Graph TheoryHardEulerian and Hamiltonian Graphs
Eulerian and Hamiltonian Graphs · Hard problem
The wheel graph has a hub joined to all vertices of a -cycle rim, plus the rim edges ( edges total, every vertex odd degree). What is the minimum number of EDGES that must be deleted (keeping the graph spanning all vertices and connected) so the result has an Euler TRAIL (allowing up to odd vertices, not necessarily )?