Lesson 15

Theorem (Jaeger, 1979). Every \(4\)-edge-connected graph has a nowhere-zero \(4\)-flow.

Proof. By Nash-Williams' theorem, the graph contains two edge-disjoint spanning trees \(T_{1}\) and \(T_{2}\). Using the parity claim for \(T_{i}\), choose \(A_{i}\subseteq T_{i}\) such that \(F_{i}=(E\setminus T_{i})\cup A_{i}\) is even. Because \(T_{1}\) and \(T_{2}\) are edge-disjoint, every edge is missing from at least one of them. Therefore \(F_{1}\cup F_{2}=E\). By the even-subgraph lemma with \(p=2\), the graph has a nowhere-zero \(4\)-flow.◼

Theorem (Jaeger, 1979). Every \(2\)-edge-connected graph has a nowhere-zero \(8\)-flow.

Proof. We work with \(\Gamma=\mathbb{Z}_{2}^{3}\). The proof is by induction on the number of edges.

Suppose first that the graph has a \(2\)-edge cut \(\{e_{1},e_{2}\}\) separating \(V\) into sides \(A\) and \(B\). Form a smaller graph \(G_{A}\) by contracting all of \(B\) to a single new vertex \(b^{*}\): the edges of \(G_{A}\) are the edges of \(G\) inside \(A\), together with \(e_{1}\) and \(e_{2}\) now joining their \(A\)-endpoints to \(b^{*}\). Define \(G_{B}\) symmetrically. The side \(B\) is connected in \(G\), being a component of \(G\setminus\{e_{1},e_{2}\}\), so \(G_{A}\) is obtained from \(G\) by contracting a connected vertex set. If \(G_{A}\) had a bridge \(e\), then \(G_{A}\setminus e\) would be disconnected, and since contraction preserves connectedness, \(G\setminus e\) would be disconnected too, contradicting the bridgelessness of \(G\). So \(G_{A}\) is bridgeless; the same argument gives bridgelessness of \(G_{B}\). Each graph has strictly fewer edges than \(G\), so by induction both admit nowhere-zero \(\mathbb{Z}_{2}^{3}\)-circulations \(\phi^{A}\) and \(\phi^{B}\).

Orient \(e_{1}\) and \(e_{2}\) both from \(A\) to \(B\). The cut lemma applied to the one-vertex side \(\{b^{*}\}\) in \(G_{A}\) gives \(\phi^{A}(e_{1})+\phi^{A}(e_{2})=0\), and since every element of \(\mathbb{Z}_{2}^{3}\) is its own inverse, \(\phi^{A}(e_{1})=\phi^{A}(e_{2})\). The same holds in \(G_{B}\). If \(\phi^{A}(e_{1})\ne\phi^{B}(e_{1})\), replace \(\phi^{B}\) by \(\sigma\circ\phi^{B}\), where \(\sigma\) is any linear automorphism of \(\mathbb{Z}_{2}^{3}\) sending \(\phi^{B}(e_{1})\) to \(\phi^{A}(e_{1})\). Automorphisms preserve nonzero-ness and the conservation law, so \(\sigma\circ\phi^{B}\) is still a nowhere-zero circulation on \(G_{B}\), and now \(\sigma(\phi^{B}(e_{1}))=\phi^{A}(e_{1})\), which forces \(\sigma(\phi^{B}(e_{2}))=\phi^{A}(e_{2})\) as well. Gluing \(\phi^{A}\) on the edges of \(A\) together with the cut edges, and \(\phi^{B}\) on the edges of \(B\), gives a nowhere-zero \(\mathbb{Z}_{2}^{3}\)-circulation on \(G\).

It remains to handle the case when the graph is \(3\)-edge-connected. Replace every edge by two parallel copies. The new graph is \(6\)-edge-connected, so by Nash-Williams' theorem it contains three edge-disjoint spanning trees \(T'_{1},T'_{2},T'_{3}\). For each \(i\), let \(T_{i}\) be the projection of \(T'_{i}\) back to the original graph: the set of edges of \(G\) at least one of whose two copies lies in \(T'_{i}\). The two parallel copies of an edge form a \(2\)-cycle in \(G'\), so a spanning tree contains at most one of them; hence \(T_{i}\) has exactly \(|V|-1\) distinct edges and is itself a spanning tree of \(G\). Since each original edge has only two copies but there are three edge-disjoint trees, for every edge \(e\) there is an index \(i\) such that \(e\notin T_{i}\).

Apply the parity claim to each \(T_{i}\) and obtain even subgraphs \(F_{i}=(E\setminus T_{i})\cup A_{i}\). The previous paragraph shows that \(F_{1}\cup F_{2}\cup F_{3}=E\). By the even-subgraph lemma with \(p=3\), the graph has a nowhere-zero \(8\)-flow.◼

So the bridge obstruction is the only obstruction if we allow the number \(8\). The hard part of the theory is to lower this number. Seymour's theorem brings it down to \(6\) unconditionally; the \(5\)-flow and \(3\)-flow conjectures predict that, with enough edge-connectivity, even smaller targets should suffice.