Lesson 3

We will need two small tools. The first one says that, when searching for even cycles, we may pass to a bipartite subgraph and lose at most half of the edges. Lemma. Every graph \(G\) contains a bipartite subgraph \(G'\) such that \[e(G')\ge \frac{e(G)}{2}.\]

Proof. Split the vertices of \(G\) into two parts \(A\) and \(B\) so that the number of edges inside the parts is as small as possible. We keep only the edges going between \(A\) and \(B\).

For every vertex \(a\in A\), the number of its neighbors inside \(A\) is at most the number of its neighbors in \(B\); otherwise, moving \(a\) to \(B\) would decrease the number of internal edges. The same is true with \(A\) and \(B\) interchanged. Summing these inequalities over all vertices, we see that the number of internal edges is at most the number of crossing edges. Hence crossing edges form at least half of all edges.◼

The second tool is a standard pruning argument. Lemma. If \(d>0\) and a graph \(G\) has \(e(G)\ge d\cdot v(G)\), then it contains a non-empty subgraph with minimum degree greater than \(d\). Proof. Repeatedly delete a vertex of degree at most \(d\), as long as such a vertex exists. If all vertices were deleted, then during the whole process we would delete fewer than \(d\cdot v(G)\) edges: the last deleted vertex would have degree \(0\). This contradicts \(e(G)\ge d\cdot v(G)\). Thus, something remains, and the remaining subgraph has minimum degree greater than \(d\).◼