Flows and Connectivity · Flow Polynomial (Optional)

Lesson 12

Nikolai Chukhin · Alexander S. Kulikov

The cut lemma showed that a bridge is an obstruction. It is natural to ask how close the converse is: does high edge-connectivity force a nowhere-zero flow with small values? This is a famous circle of questions around Tutte's flow conjectures.

Tutte's \(3\)-flow conjecture predicts that every \(4\)-edge-connected graph has a nowhere-zero \(3\)-flow. An older and broader conjecture of Tutte, the \(5\)-flow conjecture, predicts that every bridgeless graph has a nowhere-zero \(5\)-flow. Both are still open. Several beautiful weaker theorems are known:

every \(4\)-edge-connected graph has a nowhere-zero \(4\)-flow;

every \(2\)-edge-connected graph has a nowhere-zero \(8\)-flow;

every \(2\)-edge-connected graph has a nowhere-zero \(6\)-flow! (Seymour's theorem).

The \(6\)-flow theorem is deeper than what we will prove here. We prove the \(4\)-flow and \(8\)-flow theorems below; the key tool is a reformulation of nowhere-zero \(2^{p}\)-flows in terms of even subgraphs, which we develop next.