Cycles · Cycles of Even Length (Optional)
Lesson 1
In this section, we look at a question that sounds very natural after all the discussion of cycles:
How many edges force a graph to contain a cycle of a given length?For odd cycles the answer is delicate: a complete bipartite graph has many edges and no odd cycles at all. Even cycles behave much better. A dense enough graph does not merely contain one even cycle; it contains cycles of many even lengths at once!
The result below is a classical theorem of Bondy and Simonovits. The constants are not important for us. Roughly speaking, in a graph with \(n^{1+1/k}\) edges there are all even cycle lengths up to about \(n^{1/k}\).
Theorem (Bondy–Simonovits, 1974). Let \(G\) be a connected graph, let \(n=v(G)\), and let \(k\in\mathbb{N}\). If \[e(G)>18k\cdot n^{1+1/k},\] then, for every natural number \(\ell\) satisfying \(k\le \ell\le k n^{1/k}\), the graph \(G\) contains a cycle of length \(2\ell\).