Graph TheoryHardEulerian and Hamiltonian Graphs
Eulerian and Hamiltonian Graphs · Hard problem
The Möbius ladder has vertices arranged in a cycle () plus the "long" edges joining each vertex to the one steps away (), so every vertex has degree . By how much does the minimum degree fall short of the Dirac threshold ? Separately, what is the minimum number of new edges needed to add so the graph gains an Euler circuit? Report the SUM of these two numbers.