MathCastle
Graph TheoryHardGraph Coloring

Graph Coloring · Hard problem

The wheel W7W_7 has a hub vertex joined to all 77 rim vertices of the 77-cycle 1-2-3-4-5-6-7-11\text{-}2\text{-}3\text{-}4\text{-}5\text{-}6\text{-}7\text{-}1 (1414 edges in all). What is the minimum number of RIM edges that must be deleted so that the graph left behind can be properly colored with only 33 colors?