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.