MathCastle
Graph TheoryHardEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Hard problem

The Möbius ladder M8M_8 has 88 vertices 0,…,70,\ldots,7 arranged in a cycle (01,12,…,7001,12,\ldots,70) plus the 44 "long" edges joining each vertex to the one 44 steps away (04,15,26,3704,15,26,37), so every vertex has degree 33. By how much does the minimum degree fall short of the Dirac threshold n/2n/2? 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.