MathCastle
Graph TheoryMediumBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Medium problem

Men A,B,CA,B,C rank women as A:X,Y,ZA: X,Y,Z;   B:Y,Z,X\;B: Y,Z,X;   C:Z,X,Y\;C: Z,X,Y. Women rank men as X:A,B,CX: A,B,C;   Y:B,C,A\;Y: B,C,A;   Z:C,A,B\;Z: C,A,B (so every person's own top choice is actually free to accept them). For the matching A-Z,B-X,C-YA\text{-}Z, B\text{-}X, C\text{-}Y (each person's LAST choice), how many blocking pairs does it have?