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 the edges 1a,1b,2a,2b,2c,3c,3d,4d,4e,5e1a,1b,2a,2b,2c,3c,3d,4d,4e,5e. How many of these 1010 edges belong to EVERY maximum matching of this graph (not just some maximum matching)?