Tutte's Nowhere-Zero 3- 4- and 5-Flow Conjectures

A *k-flow* in a graph assigns to each edge a direction and a
value 0,1, ... ,k-1 such that at each vertex the sum of the flows
directed in equals the sum of the flows directed out. The flow is *nowhere-zero*
if zero is not assigned to an edge.

**Conjecture [T1]:** *Every bridgeless graph has a
nowhere-zero 5-flow.*

The conjecture is stated in terms of integer flows. It is equivalent to consider flows from the integers modulo five [T1].

Suppose that a graph is embedded in an orientable surface such that the faces are properly 5-colored. We let the colors be the integers modulo 5. This face coloring induces a 5-flow by assinging each edge the difference between the colors on either side of the face. Since the coloring is proper, the flow is nowhere-zero. It follows that Tutte's conjecture is true for planar graphs and for other large classes of graphs. However, since Tutte's conjecture does not involve planarity, it is much more general.

The value 5 cannot be strengthened since the Petersen graph does not have a nowhere-zero 4-flow. However, Tutte conjectured the following.

**Conjecture [T2]:** *Every bridgeless graph without a
subdivision of the Petersen graph has a nowhere-zero 4-flow.*

This 4-flow conjecture is strictly stronger than the Four Color
Theorem, so a proof is expected to be difficult. We refer the reader to
the surveys by Younger [Y] and Jaeger [J] for more details. A weaker
conjecture was that every cubic bridgeless graph without a subdivision
of the Petersen graph is 3-edge-colorable. This was recently proven by
Robertson, Sanders, Seymour, and Thomas.

**Conjecture [T3]:** *Every 4-connected graph has a
nowhere-zero 3-flow.
*

Jaeger [J] showed that every 4-connected graph has a nowhere-zero
5-flow. He points out that it is not even known if there is a k such that every k-edge-connected graph has a
nowhere-zero 3-flow.

References:

[J] F. Jaeger, Flows and generalized coloring theorems in graphs, *J.
Combin. Theory Ser. B* **26** (1979) 205-216.

[T1] W.T. Tutte, A contribution to the theory of chromatic
polynomials, *Canad. J. Math.* **6** (1954) 80-91.

[T2] W.T. Tutte, On the algebraic theory of graph colourings, *J.
Combin. Theory* **1** (1966) 15-50.

[Y] D.H. Younger, Integer flows, *J. Graph Theory* **7**
(1983) 349-357.

Submitted by: Dan Archdeacon, Department of Mathematics and Statistics, University of Vermont, Burlington VT 05405 USA.

Send comments to *dan.archdeacon@uvm.edu*

August, 1995, updated December 2003.