Lesson 4

The main trick in the proof is to look at special colorings of vertices.

A coloring \(\rho\) of the vertices of a graph is called \(t\)-periodic if the endpoints of every simple path of length \(t\) have the same color. For example, a \(2\)-periodic coloring says that vertices at distance two along any simple path have the same color. In a connected graph this almost forces a bipartite coloring by the following lemma.

Lemma. Let \(\rho\) be a coloring of the vertices of a connected graph \(H\) such that, for every vertex \(a\in V(H)\), all vertices in \(N_{H}(a)\) have the same color. Then \(\rho\) uses at most two colors.

Proof. Take a spanning tree \(T\) of \(H\) and root it at an arbitrary vertex \(a\). The vertices at level \(0\) have the color of \(a\). All vertices at level \(1\) are neighbors of \(a\), so they all have one common color. Now suppose we know that all vertices at level \(i-2\) have one color. Let \(x\) be a vertex at level \(i\), let \(y\) be its parent, and let \(z\) be the parent of \(y\). Since \(x,z\in N_{H}(y)\), the vertices \(x\) and \(z\) have the same color. Hence all even levels have one color and all odd levels have one color.◼

Corollary. If a coloring of the vertices of a connected graph is \(2\)-periodic, then it uses at most two colors.

Proof. For every vertex \(a\), any two of its neighbors are connected by a path of length two through \(a\). Therefore all neighbors of \(a\) have the same color, and the previous lemma applies.◼