Lesson 11

There is one more convention that is often used in graph theory. A nowhere-zero \(k\)-flow on an undirected graph is an orientation of the edges and integer values from \([k - 1]\) such that the incoming sum equals the outgoing sum at every vertex, now as an equality of ordinary integers.

This looks stronger than a nowhere-zero \(\mathbb{Z}_{k}\)-circulation, because equality over the integers is stronger than equality modulo \(k\). Tutte proved that, for existence, the two notions are actually equivalent.

Theorem (Tutte, 1950). An undirected graph has a nowhere-zero \(k\)-flow if and only if it has a nowhere-zero \(\mathbb{Z}_{k}\)-circulation.

Proof. One direction is immediate: reduce all integer values modulo \(k\).

For the other direction, start with a nowhere-zero \(\mathbb{Z}_{k}\)-circulation. Choose an orientation and represent every edge value by an integer in \([k - 1]\). Among all such choices, pick one minimizing \[M=\sum_{v\in V}|b(v)|, \quad \text{ where }b(v)=\sum_{e\in\delta^+(v)}\phi(e)-\sum_{e\in\delta^-(v)}\phi(e) \ .\] Since we have a circulation modulo \(k\), every \(b(v)\) is divisible by \(k\). If all \(b(v)\) are zero, we already have an integer \(k\)-flow.

Otherwise, let \(S=\{v:b(v)>0\}\) and \(T=\{v:b(v)<0\}\). Both sets are nonempty, since the sum of all \(b(v)\) is zero. Let \(U\) be the set of vertices reachable from \(S\) by directed paths in the current orientation. If \(U\) did not meet \(T\), then \(\sum_{u\in U}b(u)>0\). But no edge leaves \(U\), so this sum is nonpositive, a contradiction. Thus there is a directed path from some \(s\in S\) to some \(t\in T\).

Reverse all edges on this path, and replace each value \(a\) on the path by \(k-a\). This is still a nowhere-zero \(\mathbb{Z}_{k}\)-circulation. For internal vertices of the path, \(b(v)\) does not change. For the first vertex, \(b(s)\) decreases by \(k\); for the last vertex, \(b(t)\) increases by \(k\). Since \(b(s)>0\) and \(b(t)<0\), the value of \(M\) decreases. This contradicts the minimality of our choice. Therefore the minimum possible value of \(M\) is \(0\), and an integer \(k\)-flow exists.◼

As a consequence, if a graph has a nowhere-zero \(k\)-flow, then it also has a nowhere-zero \(k'\)-flow for every \(k'\ge k\): the same integer values are still allowed. Combining this with the theorem that only the group size matters, if a graph has a nowhere-zero \(\Gamma\)-circulation, then it has a nowhere-zero \(\Gamma'\)-circulation for every finite abelian group \(\Gamma'\) with \(|\Gamma'|\ge |\Gamma|\).