Graph TheoryHardEulerian and Hamiltonian Graphs
Eulerian and Hamiltonian Graphs · Hard problem
The Petersen graph has vertices with an outer -cycle, inner pentagram, and spokes connecting corresponding vertices. Consider two adjacent vertices in the graph, say and (which are neighbors in the outer -cycle). How many Hamiltonian paths exist that start at , visit all other vertices exactly once, and end at ?