MathCastle
Graph TheoryEasyEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Easy problem

A graph on 99 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 44). By how much does this graph's minimum degree fall short of the Dirac threshold n/2n/2?