Math Conjectures

Tutte's 55-Flow Conjecture

OPENLandmarkConjectureProposed 1954 · Standard version

Canonical statement

Every finite bridgeless loopless multigraph GG admits an orientation of its edges and a function φ:E(G)→{1,2,3,4}\varphi:E(G)\to\{1,2,3,4\} such that, for every vertex vv,
∑e∈δ+(v)φ(e)≡∑e∈δ−(v)φ(e)(mod5). \sum_{e\in\delta^+(v)}\varphi(e) \equiv \sum_{e\in\delta^-(v)}\varphi(e)\pmod 5.
Here δ+(v)\delta^+(v) and δ−(v)\delta^-(v) are respectively the sets of edges directed out of and into vv.
View source LaTeX
Every finite bridgeless loopless multigraph \(G\) admits an
orientation of its edges and a function
\(\varphi:E(G)\to\{1,2,3,4\}\) such that, for every vertex \(v\),
\[
  \sum_{e\in\delta^+(v)}\varphi(e)
  \equiv
  \sum_{e\in\delta^-(v)}\varphi(e)\pmod 5.
\]
Here \(\delta^+(v)\) and \(\delta^-(v)\) are respectively the sets of
edges directed out of and into \(v\).
GRAPH-003:[Tutte1954Flows][Seymour1981SixFlow][WestTutte5Flow]
Graph theoryCombinatorics

Notes

A nowhere-zero 55-flow on a graph GG is an orientation of its edges together with values φ(e)∈{1,2,3,4}\varphi(e)\in\{1,2,3,4\} such that flow is conserved modulo 55 at every vertex. Tutte conjectured in 1954 that every bridgeless graph admits such a flow [Tutte1954Flows]. The conjecture arose from his theory of flows as the dual of coloring: for planar graphs the statement is equivalent, via duality, to the five-color theorem, so it extends a classical coloring fact to all bridgeless graphs.

The nearest universal result is Seymour's theorem that every bridgeless graph has a nowhere-zero 66-flow [Seymour1981SixFlow]. A standard reduction shows that a minimal counterexample would have to be a snark, and nowhere-zero 55-flows have been constructed for many classes of graphs; see West's account of the problem [WestTutte5Flow].

Despite this, no proof covers every bridgeless graph, and closing the gap between Seymour's 66-flow theorem and the conjectured value 55 remains open.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.