MathCastle
Graph TheorySuperchallengeEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Superchallenge problem

The Petersen graph has 1010 vertices arranged in two rings: an inner pentagon 0,1,2,3,40,1,2,3,4 where each is connected to its two neighbors, and an outer pentagon 5,6,7,8,95,6,7,8,9 (similarly connected), plus five spokes connecting ii to i+5i+5 for i=0,…,4i=0,\ldots,4. Consider two adjacent vertices in this graph, say 00 and 11 (connected by an edge). How many distinct Hamiltonian paths start at vertex 00 and end at vertex 11 (the other endpoint of their shared edge)?