MathCastle
Graph TheorySuperchallengeBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Superchallenge problem

A graph has a 99-cycle 1-2-⋯-9-11\text{-}2\text{-}\cdots\text{-}9\text{-}1, plus two extra chords 1-51\text{-}5 and 1-61\text{-}6. First, find the minimum number of edges that must be removed to make the graph bipartite. Then, using that minimum number of removals, find the maximum matching of the resulting bipartite graph. Give the matching number of the resulting graph.