MathCastle
Graph TheorySuperchallengeBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Superchallenge problem

X={1,2,3,4,5}X=\{1,2,3,4,5\} and Y={a,b,c,d,e}Y=\{a,b,c,d,e\} are joined by every edge of K5,5K_{5,5} except 1a,2b,3c,4d,5e1a,2b,3c,4d,5e AND 1b1b (six forbidden pairs total). How many perfect matchings does this graph have?