Problem
COM-B2-M04-P007 Minimum Degree and a Cycle
#7
★★★☆☆ Level 3 of 5
In a finite graph, every vertex has degree at least \(2\). Prove that the graph contains a cycle.
Consider a longest path and its last endpoint.
Choose a longest path \(v_1v_2\ldots v_k\). All neighbours of \(v_k\) lie on this path; otherwise the path could be extended.
Since the degree of \(v_k\) is at least \(2\), besides \(v_{k-1}\) it has another neighbour on the path. Let it be \(v_i\), where \(i
A very important combination: longest path plus a degree condition.