An approximation approach to the 5-flow conjecture of Tutte

William Tutte was one of the founders of modern graph theory. He left his mark on almost all aspects of graph theory, and both solved hard problems and created much of the foundations of graph theory. He was a Fellow of the Royal Society, and won many other awards for his seminal work.

Today I will talk about a new result that is joint with Atish Das Sarma. It concerns a famous open problem of Tutte, and a new approach to the problem.

Peter Tait thought he had proved the four color theorem in 1880. He did prove that the four color theorem was equivalent to proving that every cubic bridgeless planar graph was three edge colorable. He then “proved” that there was always a three edge coloring by asserting the following: every such graph has a Hamiltonian Cycle. If this was true—it is not—then there is an easy way to three-color the edges. Color the edges on the cycle alternately green and blue. Then, color all the remaining edges yellow. This is a legal three coloring.

The cycle must have an even number of edges; otherwise, the alternation of colors will fail. I once got a negative referee report back on a paper from an unnamed conference, saying this was a problem—what if the Hamiltonian Cycle had an odd number of edges. Well, the number of edges on such a cycle is the same as the number of vertices. And, of course, every cubic graph has an even number of vertices. The proof of this is simple: the degree of each node is ${3}$ so the ${n}$ vertices have

$\displaystyle 3n/2$

edges. Clearly, this forces ${n}$ to be even, since we cannot have graphs with a fractional number of edges. Oh well.

The statement of Tait stood for decades, until Tutte thought about it. In 1946 he discovered the following graph:

This graph is easily seen to be cubic, planar, and bridgeless. Also a simple case argument shows there is no Hamiltonian Cycle. Tait was wrong, and his proof of the four color theorem was incorrect. It would be exactly thirty years until a proof of the Four-Color Theorem would be found, but a computer proof, a proof nonetheless by Kenneth Appel and Wolfgang Haken.

Flow Conjectures

Suppose that ${G=(V,E)}$ is a undirected graph. Direct the edges of the graph in any manner at all; it will turn out not to make any difference. Then a flow is a mapping ${\phi}$ from the edges ${E}$ to the integers, so that Kirchhoff’s Rule is satisfied: the amount flowing into each vertex is the same as the amount flowing out of the vertex. Formally, for each vertex ${v}$, let ${A^{+}_{v}}$ be the edges directed to ${v}$ and ${A^{-}_{v}}$ the edges directed from ${v}$. Then

$\displaystyle \sum_{e \in A^{+}_{v}} \phi(e) = \sum_{e \in A^{-}_{v}} \phi(e).$

A flow is a ${k}$-flow if the values ${\phi(e)}$ are all in the range

$\displaystyle -(k-1),\dots,0,\dots,k-1.$

It is called a called nowhere-zero ${k}$-flow provided ${\phi(e)}$ is never ${0}$.

Tutte made a number of conjectures about nowhere-zero flows on graphs; he was motivated by the coloring theorems for planar graphs. His conjectures have been partially solved, but some are still open. In particular he conjectured:

Conjecture: Every bridgeless graph has a nowhere-zero ${5}$-flow.

The best known to date is François Jaeger’s 8-flow theorem and Paul Seymour’s 6-flow theorem. See this for a nice survey of what is known about flows.

Tensor Trick

One of the powerful ideas in science and mathematics is the notion of amplification. I have discussed this before—see this. Sometimes amplification is called the Tensor Trick: it is a simple idea, but can yield surprisingly powerful consequences.

Theorem: Suppose all bridgeless graphs on ${n}$ vertices have ${5}$-flows with ${o(n)}$ zeroes. Then, the nowhere-zero ${5}$-flow conjecture is true.

Sketch of Proof

The proof is based on the notion of amplification. Suppose that ${G}$ is a graph that is a counter-example graph. That is, every ${5}$-flow on ${G}$ has at least one zero. Then we construct another graph ${H}$ that contains many copies of ${G}$. Moreover, if there is a flow on ${H}$ that has ${o(n)}$ zeroes, then there is a way to recover a perfect nowhere-zero flow for ${G}$.

More precisely, assume that ${G}$ is a bridgeless graph without a nowhere-zero ${5}$-flow. Create many copies of ${G}$ and attach them via two edges to a cycle. In the picture below, the blue graphs are copies of ${G}$, and the yellow cloud is a cycle.

Call this resulting graph ${H}$. It is important to see how we do this attachment. We take an edge ${e}$ of ${G}$ and split it into three edges ${x,y,z}$ and add edges ${a,b}$ to the cycle. See the picture below.

For enough copies of ${G}$ there must be a ${5}$-flow of ${H}$ with so few zeroes that one copy of ${G}$ and its extra edges are all non-zero. The last step of the proof is to argue that we can use these values on ${G}$ and the extra edges to create a valid nowhere-zero flow for ${G}$.

Recall we added the extra two edges to ${G}$ as in the following figure. We are using the edge labels to also stand for their values—to avoid excessive notation.

The flow must satisfy

$\displaystyle \begin{array}{rcl} x &=& y + a \\ z &=& y + b \\ a &=& b \end{array}$

The last equality holds since the net flow into a subgraph must be ${0}$. Then it is easy to see that ${x = z}$. This shows we can collapse and join the edge ${x}$ and ${z}$ into one, since they have the same value. This collapse forms the original graph ${G}$, since this replaces the edge we split into three pieces. Note, the resulting flow is non-zero, and this yields a nowhere-zero ${5}$-flow for ${G}$.

Open Problems

Can these tensor results be used to actually prove the nowhere-zero ${5}$-flow conjecture?

Can the same tensor ideas be used on other open questions concerning graphs? We believe it can also work on Tutte ${4}$-flow conjecture, but there are some details to be checked. The above method does not depend on the flow being a ${5}$-flow. Tutte’s nowhere-zero ${4}$-flow conjecture has an additional constraint on the family of graphs, since some bridgeless graphs do not have ${4}$-flows.

The tensor method may apply, we think, to other graph conjectures like the Double Cover Conjecture. See Melody Chan’s 2009 paper for details.

1. June 2, 2010 5:07 pm

See my algorithmic three edge coloring of the bridgeless cubic planar graphs.

1. http://www.flickr.com/photos/49058045@N00/4452379002/
(Edge three coloring of the Grinberg- graph)
2. http://www.flickr.com/photos/49058045@N00/710394490/
3. http://arxiv.org/abs/math/0507127
(Spiral Chains: The Proofs of Tait’s and Tutte’s Three-Edge-Coloring Conjectures)

2. June 3, 2010 2:28 pm

Amongst the numerous discoveries made by William Tutte one that I found pretty remarkable (because it is easy enough for me to understand) concerns the problem of tiling a bigs square with smaller squares all of which have different sizes.

The wonderful method Tutte and party used at Cambridge when they were around 19 or 20 involved a detour among all things to electrical networks which almost magically solved the problem.

I came across his work in a book by Martin Gardner who sadly passed away on May 22 this year.

June 4, 2010 8:06 am

Could you please explain this statement in a bit more detail –

“For enough copies of {G} there must be a {5}-flow of {H} with so few zeroes that one copy of {G} and its extra edges are all non-zero.”

I am sorry but I could not follow this one.

June 4, 2010 12:09 pm

Naman,

Sure, I was pretty brief. The graph H has cn vertices for a fixed c that depends just on the size of G. So let n be large. Then, the number of edges with zeroes is by assumption o(n). So eventually, cn >> o(n) and so one whole copy of G must be zero free. Otherwise, there would be too many zeroes.

I hope this helps.

June 4, 2010 8:48 am

Pardon me if the doubt is a bit trivial, but I don’t understand how the following holds…
“For enough copies of {G} there must be a {5}-flow of {H} with so few zeroes that one copy of {G} and its extra edges are all non-zero.”

Please reply or give a pointer to relevant pointer to the concept.

July 13, 2010 3:10 pm

Say there are $x$ copies of $G$, $G$ has $i$ vertices and the cycle has $j$ vertices.
Then, the graph $H$ has $x(i+2)+j$ vertices and there are only $Z = o(x(i+2)+j)$ zeroes.
This means that as $x \rightarrow \infty$, $\tfrac{x(i+2)+j}{Z} \rightarrow \infty$. So
$\lim_{x \rightarrow \infty} \frac{x(i+2)+j}{Z} = \lim_{x \rightarrow \infty} (i+2)\frac{x}{Z}+\frac{j}{Z} = \infty$
$\lim_{x \rightarrow \infty} \frac{x}{Z} = \infty$
For $x$ large enough, $x>Z$. By pigeonhole, there must be a copy of $G$ without zeroes.

July 13, 2010 4:13 pm

Not sure what this means…