MathCastle
Graph TheoryEasyBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Easy problem

A graph is a single cycle on nine vertices 1,2,…,91,2,\dots,9, with edges 12,23,34,45,56,67,78,89,9112,23,34,45,56,67,78,89,91. What is the minimum number of edges that must be removed so that the remaining graph is bipartite?