MathCastle
Graph TheoryChallengeBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Challenge problem

Men A,B,C,DA,B,C,D rank women W,X,Y,ZW,X,Y,Z as A ⁣: ⁣W,X,Y,ZA\!:\!W,X,Y,Z; B ⁣: ⁣X,W,Z,YB\!:\!X,W,Z,Y; C ⁣: ⁣Y,W,X,ZC\!:\!Y,W,X,Z; D ⁣: ⁣Z,Y,X,WD\!:\!Z,Y,X,W. Women rank men as W ⁣: ⁣B,A,D,CW\!:\!B,A,D,C; X ⁣: ⁣A,C,B,DX\!:\!A,C,B,D; Y ⁣: ⁣D,B,A,CY\!:\!D,B,A,C; Z ⁣: ⁣C,A,D,BZ\!:\!C,A,D,B. For the matching A-Z,B-Y,C-X,D-WA\text{-}Z, B\text{-}Y, C\text{-}X, D\text{-}W, how many blocking pairs does it have?