MathCastle
Graph TheoryEasyEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Easy problem

The Petersen graph has 1010 vertices and is 33-regular: each vertex is connected to exactly 33 others. The graph is built from a 55-cycle (vertices 0,…,40,\ldots,4), an inner pentagram (vertices 5,…,95,\ldots,9), and spokes connecting each ii to i+5i+5 (indices mod 55). How many vertices of the Petersen graph have odd degree?