Lesson 9

Assume, for contradiction, that \(G'\) has no cycle of length \(2\ell\). Pick a vertex \(c\) and split the vertices into levels \[V_{0}=\{c\}, V_{1}, V_{2},\dotsc,\] where \(V_{i}\) consists of vertices at distance \(i\) from \(c\). Since \(G'\) is bipartite, every edge goes between two neighboring levels (i.e. there are no edges between vertices inside one level). Let \(m_{i}=e_{G'}(V_{i},V_{i+1})\).

First, let us prove the following estimate for the number of edges between two neighboring levels: \[m_{i}\le 2\ell(|V_{i}|+|V_{i+1}|) \qquad\text{for }i<\ell.\] Consider any connected component \(H\) of the graph induced by \(V_{i}\cup V_{i+1}\). If \(e(H)>2\ell v(H)\), we will construct a cycle of length \(2\ell\), contradicting the assumption. This construction is the most non-trivial part of the proof, so let's do it carefully.