Nowhere zero 6-flows

A flow on a graph $G$ is an assignment to each edge of $G$ of a direction and a non-negative integer (the flow in that edge) such that the flows into and out of each vertex agree. A flow is nowhere zero if every edge is carrying a positive flow and (confusingly) it is a $k$ -flow if the flows on each edge are all less than $k$ . Tutte conjectured that every bridgeless graph has a nowhere zero $5$ -flow (so the possible flow values are $1, 2, 3, 4$ ). This is supposed to be a generalisation of the $4$ -colour theorem. Given a plane graph $G$ and a proper colouring of its faces by $1, 2, 3, 4$ , push flows of value $i$ anticlockwise around each face of $G$ . Adding the flows in the obvious way gives a flow on $G$ in which each edge has a total flow of $|i-j| \neq 0$ in some direction.

Seymour proved that every bridgeless graph has a nowhere zero $6$ -flow. Thomas Bloom and I worked this out at the blackboard, and I want to record the ideas here. First, a folklore observation that a minimal counterexample $G$ must be cubic and $3$ -connected. We will temporarily allow graphs to have loops and multiple edges.

We first show that $G$ is $3$ -edge-connected. It is certainly $2$ -edge-connected, else there is a bridge. (If $G$ is not even connected then look at a component.) If it were only $2$ -edge-connected then the graph would look like this.

2connected

Contract the top cross edge.

2connectedcontracted

If the new graph has a nowhere zero $6$ -flow then so will the old one, as the flow in the bottom cross edge tells us how much flow is passing between the left and right blobs at the identified vertices and so the flow the we must put on the edge we contracted. So $G$ is $3$ -edge connected.

Next we show that $G$ is $3$ -regular. A vertex of degree $1$ forces a bridge; a vertex of degree $2$ forces the incident edges to have equal flows, so the two edges can be regarded as one. So suppose there is a vertex $v$ of degree at least $4$ .

deg4

We want to replace two edges $xv$ and $yv$ by a single edge $xy$ to obtain a smaller graph that is no easier to find a flow for. The problem is that in doing so we might produce a bridge.

The $2$ -edge-connected components of $G-v$ are connected by single edges in a forest-like fashion. If any of the leaves of this forest contains only one neighbour of $v$ then there is a $2$ -edge-cut, so each leaf contains at least two neighbours of $v$ .

leaves

If there is a component of the forest with two leaves then choose $x$ and $y$ to be neighbours of $v$ from different leaves of that component.

twoleaves

Otherwise the $2$ -edge-connected components of $G-v$ are disconnected from each other. Now any such component $C$ must contain at least $3$ neighbours of $v$ , else there is a $2$ -edge-cut. If some $C$ contains $4$ neighbours of $v$ then we can choose $x$ and $y$ to be any two of them. Otherwise all such $C$ contain exactly $3$ neighbours of $v$ , in which case there must be at least two of them and we can choose $x$ and $y$ to be neighbours of $v$ in different components.

twoislands

So $G$ is $3$ -regular and $3$ -edge-connected. If $G$ is only $1$ -connected then there is no flow between $2$ -connected components, so one of the components is a smaller graph with no nowhere zero $6$ -flow. If $G$ is only $2$ -connected then because $3$ is so small we can also find a $2$ -edge-cut.

Finally, we want to get rid of any loops and multiple edges we might have introduced. But loops make literally no interesting contribution to flows and double edges all look like

doubleedge

and the total flow on the pair just has to agree with the edges on either side.

We’ll also need one piece of magic (see postscript).

Theorem. (Tutte) Given any integer flow of $G$ there is a $k$ -flow of $G$ that agrees with the original flow mod $k$ . (By definition, flows of $j$ in one direction and $k-j$ in the other direction agree mod $k$ .)

So we only need to worry about keeping things non-zero mod $k$ .

The engine of Seymour’s proof is the following observation.

Claim. Suppose that $G = G_0 \cup C_1 \cup \cdots \cup C_t$ where each $C_i$ is a cycle and the number of new edges when we add $C_i$ to $G_0 \cup C_1 \cup \cdots \cup C_{i-1}$ is at most $2$ . Then $G$ has a $3$ -flow which is non-zero outside $G_0$ .

Write $E_i$ for the set of edges added at the $i$ th stage. We assign flows to $C_t, \ldots, C_1$ in that order. Assign a flow of $1$ in an arbitrary direction to $C_t$ ; now the edges in $E_t$ have non-zero flow and will never be touched again. At the next stage, the edges in $E_{t-1}$ might already have some flow; but since $|E_{t-1}| \leq 2$ there are only two possible values for these flows mod $3$ . So there is some choice of flow we can put on $C_{t-1}$ to ensure that the flows on $E_{t-1}$ are non-zero. Keep going to obtain the desired $3$ -flow, applying Tutte’s result as required to bring values back in range.

Finally, we claim that the $G$ we are considering have the above form with $G_0$ being a vertex disjoint union of cycles. Then $G_0$ trivially has a $2$ -flow, and $3$ times this $2$ -flow plus the $2$ -flow constructed above is a nowhere-zero $6$ -flow on $G$ .

For $F \subseteq G$ , write $[F]$ for the largest subgraph of $G$ that can be obtained as above by adding cycles in turn, using at most two new edges at each stage. Let $G_0$ be a maximal collection of vertex disjoint cycles in $G$ with $[G_0]$ connected, and let $H = G - V(G_0)$ . We claim that $V(H)$ is empty. If not, then the $2$ -connected blocks of $H$ are connected in a forest-like fashion; let $H_0$ be one of the leaves.

seymourlast

By $3$ -connectedness there are three vertex disjoint paths from $H_0$ to $G_0$ . At most one of these paths travels through $H - H_0$ ; let $x$ and $y$ be endpoints of two paths that do not. These paths must in fact be single edges, as the only other way to get to $G_0$ would be to travel through $H - H_0$ . Finally, since $H_0$ is $2$ -connected it contains a cycle through $x$ and $y$ , contradicting the choice of $G_0$ .

Postscript. It turns out that Tutte’s result is far from magical; in fact its proof is exactly what it should be. Obtain a directed graph $H$ from $G$ by forgetting about the magnitude of flow in each edge (if an edge contains zero flow then delete it). We claim that every edge is in a directed cycle.

tutte

Indeed, choose a directed edge $\vec{xy}$ . Let $Y$ be the set of vertices that can be reached by a directed path from $y$ and let $X$ be the set of vertices that can reach $X$ by following a directed path. If $\vec{xy}$ is not in any directed cycle then $X$ and $Y$ are disjoint and there is no directed path from $Y$ to $X$ . But then there can be no flow in $\vec{xy}$ , contradicting the definition of $H$ .

So as long as there are edges with flow value at least $k$ , find a directed cycle containing one of those edges and push a flow of $k$ through it in the opposite direction. The total flow in edges with flow at least $k$ strictly decreases, so we eventually obtain a $k$ -flow.

Leave a Reply Cancel reply