Problem
COM-B2-M04-P015 A Long Cycle from Minimum Degree
In a finite graph, every vertex has degree at least \(k\), where \(k\ge 2\). Prove that the graph contains a cycle with at least \(k+1\) vertices.
Take a longest path and look at all neighbours of its last vertex.
Choose a longest path \(v_1v_2\ldots v_m\). All neighbours of \(v_m\) lie on this path; otherwise the path could be extended.
The vertex \(v_m\) has at least \(k\) neighbours among \(v_1,\ldots,v_{m-1}\). Let \(v_i\) be the earliest of these neighbours on the path. Then among \(v_i,v_{i+1},\ldots,v_{m-1}\) there are at least \(k\) neighbours of \(v_m\), so \(m-i\ge k\).
The path edges from \(v_i\) to \(v_m\), together with the edge \(v_m v_i\), form the cycle \(v_i v_{i+1}\ldots v_m v_i\). It has \(m-i+1\ge k+1\) vertices.
A strengthening of the basic cycle problem: one must not only find a cycle, but also estimate its length.