MathCastle
Graph TheorySuperchallengeBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Superchallenge problem

Take the graph with three 55-cycles sharing the common edge 1-21\text{-}2: cycle A=1-2-3-4-5-1A = 1\text{-}2\text{-}3\text{-}4\text{-}5\text{-}1, cycle B=1-2-6-7-8-1B = 1\text{-}2\text{-}6\text{-}7\text{-}8\text{-}1, and cycle C=1-2-9-10-11-1C = 1\text{-}2\text{-}9\text{-}10\text{-}11\text{-}1. After removing the single edge 1-21\text{-}2 (the minimum needed to make the graph bipartite), what is the size of a maximum matching in the resulting graph?