MathCastle
Graph TheoryHardBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Hard problem

A wheel W7W_7 has a hub vertex hh joined to every vertex of a 77-cycle 1-2-3-4-5-6-7-11\text{-}2\text{-}3\text{-}4\text{-}5\text{-}6\text{-}7\text{-}1 (77 rim edges plus 77 spokes). What is the minimum number of edges that must be removed so the whole graph becomes bipartite?