Lesson 4

Nowhere-zero circulations are not only about pipes: they are also a hidden way to look at edge colorings. In the edge-coloring discussion below, graphs are simple, so they have neither loops nor parallel edges.

A proper edge \(k\)-coloring of an undirected graph \(G\) is an assignment of colors from \([k]\) to the edges of \(G\) such that any two edges sharing a vertex receive different colors. The smallest such \(k\) is the chromatic index of \(G\). The chromatic index of any simple graph with maximum degree \(\Delta\) is either \(\Delta\) or \(\Delta+1\) (the famous theorem of Vizing). For cubic graphs  – graphs in which every vertex has degree exactly \(3\), this means the chromatic index is \(3\) or \(4\), and it is a hard combinatorial question to decide which. The following beautiful theorem reduces this question to the existence of a circulation.

Theorem. Let \(G\) be a simple cubic graph. Then \(G\) is \(3\)-edge-colorable if and only if \(G\) has a nowhere-zero circulation over \(\mathbb{Z}_{2}\times\mathbb{Z}_{2}\).

Proof. The group \(\mathbb{Z}_{2}\times\mathbb{Z}_{2}\) has exactly three nonzero elements: \[(1,0),\qquad (0,1),\qquad (1,1) \ .\] If \(G\) has a proper \(3\)-edge-coloring, use these three elements as the three colors. At every vertex of a cubic graph, the three incident edges have three different colors, and their sum is \((0,0)\). Since every element of this group is its own negative, the orientation of the edges does not matter. Thus we get a nowhere-zero circulation.

Conversely, suppose we have a nowhere-zero \(\mathbb{Z}_{2}\times\mathbb{Z}_{2}\)-circulation. At a vertex of degree \(3\), the three incident nonzero values must sum to \((0,0)\). The only way this can happen is that the three values are exactly \((1,0)\), \((0,1)\), and \((1,1)\). Therefore adjacent edges always receive different values, and these values form a proper \(3\)-edge-coloring.◼