Lesson 7

Let \(n_{\Gamma}(G)\) be the number of nowhere-zero \(\Gamma\)-circulations in \(G\). At first glance, this number should depend on the group itself. For example, \(\mathbb{Z}_{4}\) and \(\mathbb{Z}_{2}\times\mathbb{Z}_{2}\) have different addition tables. Surprisingly, for this counting problem only the size of the group matters.

Theorem (Tutte, 1954). If \(\Gamma\) and \(\Gamma'\) are finite abelian groups of the same size, then \(n_{\Gamma}(G)=n_{\Gamma'}(G)\) for every graph \(G\). Moreover, for every graph \(G\) there is a polynomial \(\Phi_{G}(q)\) such that \(n_{\Gamma}(G)=\Phi_{G}(|\Gamma|)\).

Proof. We induct on the number of non-loop edges. If all edges are loops, then every loop can receive any nonzero group element, and therefore \(n_{\Gamma}(G)=(|\Gamma|-1)^{|E|}\). This depends only on \(|\Gamma|\) and is a polynomial in \(|\Gamma|\).

Now let \(e\) be a non-loop edge from \(x\) to \(y\). We claim that \[n_{\Gamma}(G / e)=n_{\Gamma}(G)+n_{\Gamma}(G\setminus e) \ .\] Indeed, in \(G/e\) the endpoints \(x,y\) are merged into a single vertex \(z\). Take a nowhere-zero circulation on \(G/e\) and view its values as an assignment of nonzero elements to all edges of \(G\) except \(e\). Conservation holds at every vertex of \(G\) other than \(x\) and \(y\), since at these vertices the incident edges and their values are the same as in \(G/e\). Moreover, the surplus at \(x\) in \(G\) equals the deficit at \(y\): their difference is the conservation defect at \(z\) in \(G/e\), which is zero. Hence there is a unique group element \(\phi(e)\) that restores conservation at both vertices simultaneously. If \(\phi(e)\ne 0\), we obtain a nowhere-zero circulation on \(G\); if \(\phi(e)=0\), deleting \(e\) gives a nowhere-zero circulation on \(G\setminus e\). The construction is reversible, so the claimed identity follows.

Thus \[n_{\Gamma}(G)=n_{\Gamma}(G / e)-n_{\Gamma}(G\setminus e) \ .\] Both graphs on the right have fewer non-loop edges. By the induction hypothesis, their counts depend only on \(|\Gamma|\) and are given by polynomials. The same is true for \(G\).◼

The polynomial \(\Phi_{G}(q)\) is called the flow polynomial of \(G\).