Lesson 6

The next lemma is a small tool of the Bondy–Simonovits proof.

Lemma. Let \(t\ge 3\). Let \(\rho\) be a \(t\)-periodic coloring of the vertices of a connected graph \(H\). If \[e(H)\ge t\cdot v(H),\] then \(\rho\) uses at most two colors.

Proof. By the pruning lemma, there is a connected subgraph \(H'\) of \(H\) with minimum degree at least \(t+1\). We first show that all vertices of \(H'\) are colored in at most two colors.

Fix a vertex \(v\in V(H')\) and two of its neighbors \(a,b\in N_{H'}(v)\). Starting from \(v\), construct a simple path of length \(t-1\) that does not pass through \(a\) or \(b\). This is possible because at every step we have at most \(t\) forbidden vertices and the current vertex has at least \(t+1\) neighbors in \(H'\).

Let \(w'\) be the last vertex of this path. Then both \[a\to v\to \dotsb\to w' \qquad\text{and}\qquad b\to v\to \dotsb\to w'\] are simple paths of length \(t\). Since the coloring is \(t\)-periodic, \[\rho(a)=\rho(w')=\rho(b).\] Thus, for every vertex \(v\in V(H')\), all vertices in \(N_{H'}(v)\) have the same color. By the previous lemma, the subgraph \(H'\) uses at most two colors.

It remains to show that no other color can appear outside \(H'\). Take a  vertex \(w\in V(H)\setminus V(H')\) and a shortest path from \(w\) to \(H'\), ending at a vertex \(a\in V(H')\). Since \(H'\) has minimum degree at least \(t+1\), this path can be extended inside \(H'\) so that its total length is a multiple of \(t\). Applying \(t\)-periodicity along consecutive blocks of length \(t\), we conclude that \(w\) has the same color as some vertex of \(H'\). Hence the whole graph \(H\) uses at most two colors.◼