MathCastle
Graph TheoryMediumBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Medium problem

A graph consists of a 55-cycle on vertices 1,2,3,4,51,2,3,4,5 (edges 12,23,34,45,5112,23,34,45,51) and a 77-cycle on vertices 6,7,…,126,7,\dots,12 (edges 67,78,89,9-10,10-11,11-12,12-667,78,89,9\text{-}10,10\text{-}11,11\text{-}12,12\text{-}6), joined by one extra edge 5656. What is the minimum number of edges that must be removed so the whole graph becomes bipartite?