Lesson 10

The flow polynomial and the chromatic polynomial are more than parallel constructions: for planar graphs they are essentially the same polynomial, viewed through the lens of planar duality!

A proper face \(q\)-coloring of \(G\) is an assignment of colors from \([q]\) to the faces of \(G\) (including the unbounded outer face) such that, for every edge, the two faces lying on its two sides receive different colors.

Theorem (Tutte, 1954). Let \(G\) be a connected plane graph, and let \(F_{G}(q)\) be the number of proper face \(q\)-colorings of \(G\). Then for every \(q\ge 2\), \[F_{G}(q)=q\Phi_{G}(q) \ .\] In particular, the faces of \(G\) admit a proper \(q\)-coloring if and only if \(G\) has a nowhere-zero \(\mathbb{Z}_{q}\)-circulation.

Proof. Think of the \(q\) colors as elements of \(\mathbb{Z}_{q}\). Orient the edges of \(G\) arbitrarily. For an oriented edge \(e\), let \(L(e)\) be the face on the left of \(e\) and \(R(e)\) the face on the right. From a proper face coloring \(c\), define \[\phi(e)=c(L(e))-c(R(e)) \in \mathbb{Z}_{q} \ .\] The two faces on the sides of \(e\) have different colors, so \(\phi(e)\ne 0\). At a vertex, list the incident faces in cyclic order as \(c_{1},c_{2},…,c_{d}\). The signed contributions of the incident edges are \(c_{1}-c_{2},c_{2}-c_{3},…,c_{d}-c_{1}\), and their sum is \(0\). So \(\phi\) is a nowhere-zero circulation.

Conversely, suppose that \(\phi\) is a nowhere-zero \(\mathbb{Z}_{q}\)-circulation. Choose one face and give it color \(0\). To color any other face, walk from the starting face to it by repeatedly crossing edges of \(G\); when we cross an edge from its right side to its left side, add \(\phi(e)\), and when we cross it the other way, subtract \(\phi(e)\). We need to know that the resulting color does not depend on the sequence of edge-crossings we used. For a walk of edge-crossings that returns to the starting face, the total color change is the signed sum of \(\phi\)-values on the crossed edges; after canceling edges crossed twice in opposite directions, what remains is the circulation across the cut separating the vertices enclosed by the walk from the rest of \(G\), which is \(0\) by the cut lemma. Hence the colors are well-defined, and across every edge the two face colors differ by the nonzero value \(\phi(e)\).

Finally, two proper face colorings give the same circulation if and only if they differ by a global additive constant in \(\mathbb{Z}_{q}\): shifting every face color by the same element leaves all the differences \(\phi(e)=c(L(e))-c(R(e))\) unchanged, and once one face's color is fixed, the rest are determined by the argument above. Hence each circulation corresponds to exactly \(q\) proper face colorings, which gives \(F_{G}(q)=q\Phi_{G}(q)\).◼