There is a limpid mathematics journal at the University of Waterloo named mathNEWS, this essay was selected from that little journal. University of Waterloo’s campus has a street named William Tutte way near Davis Centre Library.
William Tutte spent enormous effort trying to solve the Four Colour Problem. Even after the computer-aided proof of Appel and Haken in 1976, Tutte continued working toward finding a short, human-readable, proof.
Tutte never did succeed, but he came close to achieving his goal on several occasions. For example, Tutte had significant insights into Tait’s Conjecture that three-connected cubic planar graphs are Hamiltonia n, which Tait had already shown to imply the Four Colour Conjecture. Unfortunately, instead of leading him to a proof, Tutte’s insights led him to discover a 46-vertex counter-example to Tait’s conjecture. Not long after that, Tutte proved that all four-connected planar graphs are Hamiltonian. While this is agonizingly close to Tait’s Conjecture, it does not have any immediate applications to colouring.
Following those attempts, Tutte tried various algebraic approaches; one of these involved the chromatic polynomial of a graph. For a graph G and non-negative integer k, let \( \lambda_G(k) \) denote the number of colourings of G with colours 1, …, k. It is not at all obvious from this definition, but \( \lambda_G \) is a polynomial, which allows us to define it at values other than the positive integers.
The Four Colour Conjecture states that \( \lambda_G(4) > 0 \) whenever G is planar. If \( 0 \leq k_1 \leq k_2 \) are integers, then any \( k_1 \)-colouring is a \( k_2 \)-colouring, and hence \( \lambda_G(k_2) \geq \lambda_G(k_1) \). This property does not extend to non-negative real numbers, but it is conjectured that for each real number \( x \geq 4 \), we have \( \lambda_G(x) > 0 \) whenever G is planar. Tutte proved the following amazing result which superficially looks stronger than the Four Colour Theorem; in this result \( \tau \) is the golden ratio, so \( \tau+2=\frac{5+\sqrt{5}}{2} \approx 3.618 \).
The 3.618 Colour Theorem. For each planar graph G, we have
\( \lambda_G(\tau+2) > 0 \).
This year Gordon Royle proved that, if \( x < 4 \) is a real number such that \( \lambda_G(x) > 0 \) for each planar graph G, then \( x = \tau+2 \). Wow!
How on earth, you may ask, did Tutte come upon his result? It turns out that he came across the idea to try \( \tau+2 \) by empirical evidence. That evidence takes the form of eight large binders that are stored in the C&O library on the sixth floor of the MC building. Each of these binders contains, at a guess, around 500 pages. The pages alternate between a beautiful hand-drawn picture of a planar graph and a computer print out of the roots of its chromatic polynomial. Tutte enlisted the help of Ruth Bari and Dick Wick Hall to systematically generate the graphs and the help of Gerry Berman, founder of the C&O Department, to compute the chromatic roots. Nevertheless, it beggars belief to consider the work that Tutte put into drawing each of the graphs by hand and then trawling through these volumes for any patterns that might provide in-roads to the elusive Four Colour Conjecture. In the end he made do with only 3.618 colours.
This article is in memory of William T. Tutte, in this the centennial year of his birth. Among other honours, Tutte was a founding member of the C&O Department, a legendary World War II code breaker, and a hugely influential combinatorialist.
- One of the most prolific graph theorists, William T. Tutte, judged the impact of the four-color theorem on mathematics by proclaiming: “The four-colour theorem is the tip of the iceberg, the thin end of the wedge, and the first cuckoo of Spring.” (The Princeton Companion to Mathematics - Part V Theorems and Problems - V.12 The Four-Color Theorem, by Bojan Mohar)
- The Colorful Problem That Has Long Frustrated Mathematicians
- I imagine one of them outgribing in despair, crying ‘What shall I do now?’ To which the proper answer is ‘Be of good cheer. You can continue in the same general line of research.’ - Bill Tutte