MathCastle
Graph TheoryHardEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Hard problem

The Petersen graph has 1010 vertices with an outer 55-cycle, inner pentagram, and spokes connecting corresponding vertices. Consider two adjacent vertices in the graph, say 00 and 11 (which are neighbors in the outer 55-cycle). How many Hamiltonian paths exist that start at 00, visit all other 88 vertices exactly once, and end at 11?