Graph TheoryEasyEulerian and Hamiltonian Graphs
Eulerian and Hamiltonian Graphs · Easy problem
A graph on vertices joins each vertex to the two vertices "one step away" and the two vertices "two steps away" around a cycle (so each vertex has degree ). By how much does this graph's minimum degree fall short of the Dirac threshold ?