MathCastle
Graph TheorySuperchallengeBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Superchallenge problem

A bipartite graph has X={1,2,3,4,5}X=\{1,2,3,4,5\} and Y={a,b,c,d}Y=\{a,b,c,d\}, where every vertex of XX has degree EXACTLY 33 (each missing exactly one of the 44 vertices of YY, though different XX-vertices may miss different ones). Over all such graphs, what is the SMALLEST possible value of the maximum matching?