Lesson 4

Let us start with undirected graphs.

Lemma. Let \(k>2\) and \(v_{1} \to v_{2} \to \dotsb \to v_{k}\) be the longest (simple) path in an undirected graph \(G\). If \(\deg(v_{1})+\deg(v_{k}) \ge k\), then \(G\) has a cycle of length \(k\).

Proof. If the graph contains the edge \(\{v_{1}, v_{k}\}\), then since \(k>2\), the graph has a cycle of length \(k\), so we assume that such an edge does not exist. The vertices \(v_{1}\) and \(v_{k}\) can only be connected to vertices of the given path (otherwise, this path would not be the longest). Let \(\deg(v_{1})=l\), then \(\deg(v_{k}) \ge k-l\). Let \(v_{i_1}, \dotsc, v_{i_l}\) be neighbors of \(v_{1}\), and let \(u_{1}, \dotsc, u_{l}\) be their predecessors in the given path. Then \(v_{k}\) must be connected to at least one of \(u_{1}, \dotsc, u_{l}\): indeed, since \(v_{k}\) is only connected to vertices of the path, if it is not connected to any of \(u_{1}, \dotsc, u_{l}\), then \(\deg(v_{k}) \le k-1-l\). Thus, let \(\{v_{i},v_{1}\}\) and \(\{v_{i-1},v_{k}\}\) be edges of our graph. Then \(v_{1} \to v_{2} \to \dotsb \to v_{i-1}\to v_{k} \to v_{k-1}\to v_{k-2}\to \dotsb \to v_{i}\to v_{1}\) forms the desired cycle of length \(k\).