Tutte's 5-flow Conjecture (1954)

Originator(s): William Tutte

Conjecture/Question: Every bridgeless graph has a nowhere-zero 5-flow.

Definitions/Background/motivation: A bridgeless graph is a graph with no cut-edge. For planar graphs, the conjecture is equivalent to the statement that all planar graphs are 5-colorable, so the conjecture generalizes that statement.

Comments/Partial results: Kilpatrick [K] and Jaeger [J] proved that every bridgeless graph is 8-flowable. Seymour [Se] proved that every bridgeless graph is 6-flowable.

Celmins proved that a smallest counterexample to 5-flowability must be a cyclically 5-edge-connected snark with girth at least 7. Steinberg [St] proved the conjecture for graphs embeddable in the projective plane.

The conjecture is implied by a conjecture of Archdeacon [1984] and Jaeger [1988] that bridgeless graphs have orientable cycle double covers of order at most 5.

References:
[Se] Seymour, P. D. Nowhere-zero $6$-flows. J. Combin. Theory Ser. B 30 (1981), no. 2, 130--135.
[St] Steinberg, Richard Tutte's $5$-flow conjecture for the projective plane. J. Graph Theory 8 (1984), no. 2, 277--289.

Keywords:

Back to Index Page Link to Glossary