MathCastle
Graph TheorySuperchallengeBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Superchallenge problem

A graph has 1111 vertices and three 55-cycles, all sharing the single 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. What is the minimum number of edges that must be removed so the whole graph becomes bipartite?