MathCastle
Graph TheoryHardEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Hard problem

The wheel graph W6W_6 has a hub HH joined to all 66 vertices of a 66-cycle rim, plus the 66 rim edges (1212 edges total, every vertex odd degree). What is the minimum number of EDGES that must be deleted (keeping the graph spanning all 77 vertices and connected) so the result has an Euler TRAIL (allowing up to 22 odd vertices, not necessarily 00)?