MathCastle
Graph TheorySuperchallengeGraph Coloring

Graph Coloring · Superchallenge problem

The Petersen graph (1010 vertices, 1515 edges, every vertex of degree 33) contains odd cycles (e.g. its outer rim is a 55-cycle), so it is not bipartite. What is the minimum number of edges that must be deleted so that the remaining graph IS bipartite?