MathCastle
Graph TheoryMediumBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Medium problem

The Petersen graph has an outer 55-cycle on vertices 1,2,3,4,51,2,3,4,5 (edges 12,23,34,45,5112,23,34,45,51), an inner 55-cycle on vertices 6,7,8,9,106,7,8,9,10 connecting each to the vertex two steps ahead (68,79,8-10,9-6,10-768, 79, 8\text{-}10, 9\text{-}6, 10\text{-}7), and 55 spokes 16,27,38,49,5-1016, 27, 38, 49, 5\text{-}10. What is the length of the shortest cycle in this graph that has odd length?