MathCastle
Graph TheoryChallengeBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Challenge problem

X={1,2,3,4}X=\{1,2,3,4\} and Y={a,b,c,d}Y=\{a,b,c,d\} are joined by every edge of K4,4K_{4,4} except 1a1a and 2a2a (both 11 and 22 are forbidden from pairing with aa; every other edge is present). How many perfect matchings does this graph have?