Graph TheoryChallengeEulerian and Hamiltonian Graphs
Eulerian and Hamiltonian Graphs · Challenge problem
From you may delete edges, as long as every vertex keeps degree at least (so Dirac's theorem still guarantees a Hamiltonian cycle). What is the largest number of edges you can delete?