MathCastle
Graph TheorySuperchallengeBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Superchallenge problem

Over all bipartite graphs with ∣X∣=∣Y∣=4|X|=|Y|=4 where every vertex of XX has degree EXACTLY 22 (but YY's degrees may vary), what is the SMALLEST possible size of a maximum matching? (A graph where all of XX can be matched would give 44.)