Tutte’s five-flow conjecture

Imagine three dots joined in a triangle. Send one unit around it in one direction: each dot receives one unit and sends one out. A graph is a collection of dots and links, and this equal-in, equal-out rule is flow conservation. Every link must carry something.

A bridge is a link whose removal disconnects the graph. It cannot carry a nonzero conserved flow: one side would gain or lose flow with no other crossing to balance it. Tutte asks whether every finite graph without bridges can choose directions and positive whole-number flows from 1 through 4 on all links. This is called a five-flow because every value is less than five.[1]

A finite graph can carry circulation with no sources or sinks: choose a direction for each edge and balance the total incoming and outgoing amounts at every vertex. Tutte's question is whether the absence of bridges, edges whose removal separates formerly connected parts, always allows every edge to carry a positive integer below five. A triangle with a cyclic orientation and amount 1 on each edge satisfies the rules; the problem concerns all bridgeless graphs, not just cycles. Such an assignment is a nowhere-zero flow.

For a chosen orientation, write the amount on edge $e$ as $f(e)$. Let $I(v)$ and $O(v)$ be the total amounts entering and leaving vertex $v$. Conservation requires $$I(v)=O(v).$$ The permitted amounts satisfy $1\leq f(e)\leq4$. Equivalently, with directions fixed arbitrarily, signed nonzero values of absolute value at most 4 may be used; a negative value reverses the actual flow direction. A cut splits the vertices into two groups. Adding the vertex equations in one group cancels internal flows and leaves only the crossing edges; a bridge is a lone crossing and must carry zero. The established six-flow theorem permits amounts through 5.[1] [2]

The claim is known for some graphs, but not every eligible graph.[1]

The cited 2014 theorem applies to graphs with three incident edges at each vertex. It requires at least six edges in any cut separating two sides that each contain a cycle, and a cover of all vertices by disjoint cycles with at most four odd-length cycles. These extra conditions do not cover every bridgeless graph. The universal six-flow theorem permits amounts through 5; the conjecture asks whether amounts through 4 always suffice.[1]

Flows and coloring offer different ways to describe the same graph structure. For graphs with three links at each dot, certain flow rules are equivalent to coloring links so that touching links have different colors. Studying flows therefore reveals more than how much can circulate.[1]

The bound has consequences for a different packing problem. In a directed graph, a one-way cut separates two vertex groups with all crossing arrows pointing the same way. A dijoin is a set of arrows meeting every such cut. The cited 2025 theorem connects a flow on the underlying undirected graph with the number of disjoint dijoins.

In that theorem's setting, if the smallest one-way cut has 30 arrows, a six-flow gives at least $30/6=5$ disjoint dijoins. A five-flow would give at least $30/5=6$. These are illustrative substitutions in the theorem, not measured network performance. Thus a tighter circulation bound can strengthen a guarantee about organizing several separate sets that each meet every one-way cut.[2]