TUTTE, WILLIAM (BILL) THOMAS

(b. Newmarket, United Kingdom, 14 May 1917, d. Waterloo, Ontario, Canada, 2 May 2002), mathematics, graph theory, cryptography.

Tutte will take his place in history for two reasons. First, as part of the famous code-breaking team at Bletchley Park, he made a significant individual contribution to the outcome of World War II. Second, he formulated and proved many of the theorems that form the foundations of graph theory. In both cases his achievements resulted from very deep insights into matters that, at first sight, might be thought simple. In 1930 Denes König, the author of the first book on graph theory, had mentioned two important outstanding problems: the conjecture of Tait and the extension of Petersen’s theorem on factorization of graphs. Both problems, “and many others,” were later settled by Tutte (Erdös, 1979, p. xxiii).

Graph theory has grown significantly in importance since that time, partly because of its links with advances in theoretical computer science. For that reason the name of Tutte is now recognized throughout the scientific community as the leading pioneer of an important branch of mathematics.

Origins. Tutte grew up in Chevely, a village near New-market, England, where his father was gardener at the Rutland Arms Hotel. He attended the village school until, at the age of eleven, he won a scholarship to the Cambridge and County High School. The school was 15 miles from his home, and the daily journey was difficult, but well worth the effort. He won many prizes, and in the school library he discovered W. W. Rouse Ball’s book of Mathematical Recreations and Essays, in which he read about the five-color theorem and Petersen’s theorem. Both these results were to figure largely in his life’s work.

In 1935 he went to Trinity College, Cambridge, to read natural sciences. He specialized in chemistry, and was awarded a first-class honors degree. He also joined the Trinity Mathematical Society, where he met R. L. Brooks, C. A. B. Smith, and A. H. Stone. Together they worked on the problem of dividing a square into squares of different sizes. The story of their work on this problem has been told many times, including by Tutte himself in Scientific American (1958). Many important ideas arose first in this work. The ideas about spanning trees can be traced back to the electrical networks of Gustav Kirchhoff, but many of the algebraic results were new, as were the insights into planarity and duality.

Code Breaking. Tutte began research in chemistry, and produced two papers on his experimental results. His progress was interrupted when he was called up for national service in World War II, and after initial training he arrived at Bletchley Park, the British cryptographic headquarters, in 1941. At his eightieth birthday celebration in 1997 he felt able to talk informally about some of the details, and soon afterward he was persuaded to give a talk at the opening of the Center for Applied Cryptographic Research at the University of Waterloo. In this talk, “FISH and I” (2000), he tells how, others having failed, he was asked to work on the cipher system known at Bletchley as Tunny. This was one of the “Fish” codes used by the German High Command. He had an idea and, although not optimistic, he “thought it best to seem busy.” So he copied out some cipher text onto sheets of squared paper, using chunks of various lengths, noticed certain patterns, and was able to infer the structure of the system. Indeed, he achieved a virtual reconstruction of an extremely complex machine using only scraps of information—an amazing feat that must rank as one of his greatest intellectual achievements.

Soon many people were helping to work out the implications of Tutte’s discovery. This work continued throughout 1942 and 1943, with regular upgrading of the techniques to deal with improvements in the system. Eventually it became necessary to use a form of number-crunching statistical analysis, and Tutte saw how this could be done. He reported his ideas and, in his own words, “there were rapid developments.” The outcome was that the famous Colossus computer was deployed on these problems.

At the end of the war, Trinity College elected Tutte to a research fellowship in mathematics. Although less prestigious in the public eye than the awards given to other civil servants, it was probably more appreciated by the recipient. Exactly how it came about is unclear. C. A. B. Smith recalled being stopped in the street by a fellow of Trinity, who said “we’ve just elected Tutte to a Fellowship but we don't know what he has done or where he lives” (Smith, 1979, pp. xix–xxi).

Graph Theory. The period at Trinity was a highly productive one. His PhD thesis on An Algebraic Theory of Graphs contained many seminal ideas, and these were published in papers that quickly established graph theory as a significant area of mathematics, with Tutte as its master builder. Among the papers that were published at that time, there are several classics. In a paper published in 1946 he disproved Tait’s conjecture by constructing a planar cubic graph that has no Hamilton cycle. His paper on the symmetry of cubic graphs contains a truly unexpected bound on the order of a vertex-stabilizer, a fact that was to resurface twenty years later in the work of permutation-group theorists. Perhaps his most influential paper is the one on factorization of graphs, in which he obtains the canonical form of the basic result on this topic, with Petersen’s theorem as a simple corollary.

Much later, in his book Graph Theory as I Have Known It (1998), he gave a fascinating account of how he arrived at some of these fundamental results. Perhaps not surprisingly, it was often by a process that offered an intellectual challenge rather than a guarantee of success. As well as graph theory, his thesis also contained important results about matroids, a subject that had been inaugurated by Hassler Whitney.

In 1948 he took up a teaching position at the University of Toronto. Here he continued to produce a stream of new ideas, including papers on aspects of the chromatic polynomial and its two-variable generalization, now known (justifiably) as the Tutte polynomial. Several famous conjectures, such as the conjecture that every bridgeless graph has a 5-flow, also appeared in print at this time.

In 1962 he was persuaded to move to the newly established University of Waterloo. By this time he had been appointed a Fellow of the Royal Society of Canada, and his eminence was being recognized internationally. The university created around him a world-famous Department of Combinatorics and Optimisation, which was instrumental in the foundation of the Journal of Combinatorial Theory.

By the 1970s the growth of air travel meant that Bill and his wife Dorothea, whom he had married in 1949, were able to travel extensively and they returned to England on several occasions. His work at this period centered on the enumeration of planar graphs, and specifically four-colorable planar graphs. There was a slight chance that the four-color conjecture could be settled “asymptotically,” but he did not have great hopes for the method. He greeted the Appel-Haken resolution of the conjecture enthusiastically, agreeing that the strategy was sound, even if the calculations could not be checked by hand.

Retirement. He retired formally in 1985, but continued to be active in mathematics. In his quiet way he enjoyed the recognition that accompanied the growth in popularity and status of graph theory, the subject he had built. Outstanding mathematicians were attracted to work in this field, many of them inspired by Tutte’s earlier results.

After Dorothea’s death in 1994 he lived in England for a while. Since there were no children from the marriage Tutte did not settle in England, and eventually returned to his adopted home in Ontario. It was proper that his eightieth birthday should be marked by a celebration in Waterloo, where he was able to talk about his work to an audience that fully appreciated what he had achieved. Two years later he spoke about “The Coming of the Matroids” (1999), explaining how some of his work at Bletchley had helped him to understand the properties of linear dependence, and how this led to some of the fundamental theorems of matroid theory. In 2001 his eminence was recognized by the award of the Order of Canada, which he received with characteristic humor and humility.

At that time he was in good health, but in March 2002 he was diagnosed with lymphoma of the spleen, and he died in May, in his eighty-fifth year.

BIBLIOGRAPHY

WORKS BY TUTTE

“Squaring the Square.” Scientific American (November 1958). Reprinted in More Mathematical Puzzles and Diversions, edited by M. Gardner. London: Penguin, 1961. Contains many interesting insights.

Selected Papers of W. T. Tutte. Edited by D. McCarthy and R. G. Stanton. St. Pierre, Manitoba, Canada: Charles Babbage Research Centre, 1979.

Graph Theory. Menlo Park, CA: Addison-Wesley, 1984. For mathematicians.

Graph Theory as I Have Known It. Oxford: Clarendon Press, 1998. The best account of his own work, written in simple terms.

“The Coming of the Matroids.” In Surveys in Combinatorics, edited by J. D. Lamb and D. A. Preece. Cambridge, U.K.: Cambridge University Press, 1999. Describes the link between his wartime work and abstract mathematics.

“FISH and I.” In Coding Theory and Cryptology, edited by D. Joyner. New York: Springer, 2000. Describes his work at Bletchley Park.

OTHER SOURCES

Erdös, P. “A Tribute.” In Graph Theory and Related Topics, edited by J. A. Bondy and U. S. R. Murty. New York: Academic Press, 1979. An evaluation by one of the leading mathematicians of the twentieth century.

Smith, C. A. B. “Early Reminiscences.” In Graph Theory and Related Topics, edited by J. A. Bondy and U. S. R. Murty. New York: Academic Press, 1979. Written by a lifelong friend.

Norman Biggs