MacTutor logo MacTutor

William Thomas Tutte

Quick Info

Born
14 May 1917
Newmarket, Suffolk, England
Died
2 May 2002
Waterloo, Canada
Summary
Bill Tutte was an English mathematician best known for his work on code-breaking in World War II.
Thumbnail of William Tutte
View six larger pictures

Biography

William Tutte's father was William John Tutte who was an estate gardener, and his mother Annie Newell was a cook and housekeeper. Bill, as he was known to his friends and colleagues, was born in Newmarket, Suffolk, England, at a time when his parents were working in Fitzroy House, the Newmarket horse racing stable. In his early years, however, Bill lived in several different towns depending on where his father was working. The longest period that the family spent in a single place was near Whitby in Yorkshire, but when Bill was five years old his father got a job at The Rutland Arms Hotel in Newmarket. Bill and his parents returned to live in the village of Cheveley about three miles to the east of the town where their cottage was beside the Cheveley village church. Shortly after this Bill started his education attending the primary school in the village.

When he was eleven years old Bill was awarded a scholarship to the Cambridge and County Day School. At this school he excelled in his studies but it was not mathematics which first inspired him for at this time his favourite subject was chemistry. Finding a copy of Rouse Ball's book Mathematical Recreations and Essays in the library while he was at this school he began to acquire a fascination with the graph theory problems he read about in this book but it was not enough to change his mind about studying chemistry at university.

In 1935 Tutte went up to Trinity College, Cambridge, to study the Natural Sciences Tripos taking chemistry as his major subject. Soon after arriving at Cambridge his interest in mathematics was sufficient to have him join the Trinity Mathematical Society and he soon made friends with several of the mathematicians. He graduated with a degree in chemistry and began research, quickly producing his first two publications which were papers on chemistry published in 1939.

It was, however, with his mathematical friends R Leonard Brooks, Cedric A B Smith and Arthur H Stone that Tutte wrote his next paper. They had found a problem in H E Dudeney's book The Canterbury puzzles and other curious problems (1931) about decomposing a rectangle RR into squares. A squaring of order nn of RR is a decomposition of the rectangle into nn non-overlapping squares. If the squares are all unequal, the squaring is called perfect, and in this case RR is called a perfect rectangle. Dehn had studied the squaring problem in 1903 and proved that a rectangle can be squared if and only if its sides are commensurable and that if it can be squared then there are infinitely many perfect squarings. In the paper which Tutte and his three friends published in the Duke Mathematical Journal in 1940 they associated a graph with a squaring and by looking at the flow of an electrical current through the graph reproved Dehn's theorems and proved many new ones.

At this stage World War II had started and Tutte was engaged in research in chemistry at Cambridge. His tutor realised that his mathematical skills would make him a valuable person to undertake work on deciphering codes at Bletchley Park and, in January 1941, he started work there. His achievements at Bletchley Park were described in the citation when he was inducted as Officer of the Order of Canada in October 2001:-
As a young mathematician and codebreaker, he deciphered a series of German military encryption codes known as FISH. This has been described as one of the greatest intellectual feats of World War II.
Although this work was for many years covered by the Official Secrets Act, Tutte felt able to talk about it at his 80th birthday celebrations in 1997. In the following year he gave the lecture "FISH and I", which is reproduced in [8], giving a fascinating account. We should perhaps give some more details of this important work.

The first FISH messages available to those in Bletchley Park for deciphering had been transmitted by the German Army in 1941 in Athens intended to be picked up in Vienna. On 30 August 1941 an error was made by a German radio operator who transmitted two long coded messages twice. Both were encoded using the same initial 12 letter code indicator, but the second message corrected punctuation in the first. Using these two messages Tutte was able to deduce the structure of the machine sending the message after four months of intense work.

By examining patterns in the characters, Tutte deduced that the machine sending the message had one wheel with 41 sprockets, and a second wheel with 31 sprockets. Working with others he finally discovered that the machine had 12 wheels and they determined how they were connected. Having worked out the structure of the encoding machine purely from the messages, a seemingly impossibly difficult task, Tutte set about writing algorithms decode FISH messages. In 1943 the sophistication of the coding was increased and hand decoding using Tutte's algorithms became too hard. A computer called Colossus was built to run Tutte's decoding algorithms and their success played a vital role towards the end of the war. Rather strangely, although many such as Turing were honoured for their contributions at Bletchley Park, Tutte never received similar honours.

At the end of World War II Tutte returned to Cambridge, but not now to complete a doctorate in chemistry but rather to study for his doctorate in mathematics. Despite having no formal qualifications at this stage, Trinity College elected Tutte to a Research Fellowship in Mathematics. He worked on algebra and graph theory, combining the two to produce his first outstanding contribution to matroid theory. It had been Whitney who had introduced the idea of a matroid in a paper in the American Journal of Mathematics in 1935. Tutte was soon publishing papers on many different aspects of graph theory.

In 1946 he published On Hamiltonian circuits, and in the following year the two papers A family of cubical graphs and A ring in graph theory. Tutte's paper The dissection of equilateral triangles into equilateral triangles (1948) follows a similar theme to his first mathematics paper on squaring rectangles. In the same year he published a paper on perhaps the most famous of all graph theory problems On the four-colour conjecture. Donald Coxeter at the University of Toronto had reviewed some of these papers and was certainly fully aware of Tutte's remarkable potential. After the award of his doctorate in 1948 Coxeter invited Tutte to take up a post at the University of Toronto. In the following year Tutte married Dorothea Mitchell; they had no children.

Tutte remained at Toronto until 1962 when he joined the faculty at the University of Waterloo. The university was only five years old when he was appointed and he soon stamped his personality on mathematics with the university creating the Department of Combinatorics and Optimisation. Bill and Dorothea moved to a home in West Montrose, along the Grand River, where Tutte continued to live after his retirement in 1984 until the death of his wife 1994. Bill Cunningham and Daniel Younger, in nominating Tutte for a major award in 2001, wrote of his time at Waterloo:-
He has contributed greatly to creating its character and establishing its reputation in combinatorial mathematics. He was an important ingredient in the recipe that produced the Faculty of Mathematics in 1967. He was named Honorary Director of the Centre for Cryptographic Research in 1998.
Tutte wrote many outstanding papers (Mathematical Reviews lists 168 papers by Tutte) and books. Among his books are: Connectivity in graphs published in 1966; Introduction to the theory of matroids (1971), based on a series of lectures given by Tutte at the Rand Corporation in 1965; Graph Theory (1984); and Graph Theory as I Have Known It (1998) which gives a fascinating account of how he discovered his many fundamental results.

The pace at which graph theory developed was quite remarkable so that when Tutte wrote Connectivity in graphs in 1966 he stated in the preface:-
Graph theory is now too extensive a subject for adequate presentation in a book of this size. Faced with the alternatives of writing a shallow survey of the greater part of graph theory or of giving a reasonably deep account of a small part, I have chosen the latter.
In fact he chose to cover results from the general theory of undirected graphs such as Euler paths, the symmetry of graphs, the girth, and results on non-separability and triple connection.

In 1984 Tutte published Graph Theory which contains a foreword written by C St J A Nash-Williams:-
It is both fitting and fortunate that the volume on graph theory in the Encyclopedia of Mathematics and its Applications has an author whose contributions to graph theory are - in the opinion of many - unequalled. Indeed, the style and content of the book betray throughout the influence of Professor Tutte's own work and the distinctive flavour of his personal approach to the subject. ... [T]his is by no means 'just another book on graph theory', since the treatment of [many of the central themes of graph theory] is unified into a coherent whole by Professor Tutte's highly individual approach. Moreover, the more customary topics are leavened with some 'pleasant surprises', such as the author's attractive theory of decomposition of graphs into 3-connected '3-blocks', an interesting and remarkable approach to electrical networks, and - perhaps particularly - the classification theorem for closed surfaces.
Tutte has received many high honours for his work. We mentioned above that he received the Order of Canada and prior to that he was elected a Fellow of the Royal Society of Canada, and a Fellow of the Royal Society of London. In 2001 Tutte received the $5,000 prize from the Centre de recherches mathématiques in Montreal and the Fields Institute for Research in Mathematical Sciences in Toronto. The citation described him as:-
... the leading world figure in graph and matroid theories. In graph theory he established fundamental results for matching, connectivity, symmetry in graphs, reconstruction, colouring, Hamiltonian circuits, graphs on higher surfaces, graph enumeration and graph polynomials. In matroid theory, he is the single most important pioneer. One deep result is his characterization of regular matroids in terms of excluded minors. Another is his characterization of graphic matroids. These have provided the foundation for substantial structural work in this area.
As to Tutte's character Norman Biggs writes in [3] that he was:-
... a very shy man [with a] placid temperament...
He also tells us that:-
His wife would bemoan the fact that weekends had to be spent on research, because Bill feared that mathematical inspiration would dry up before he was 40 (at least, that's what he told her).

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. It was proper that his 80th 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.
In 1996, he moved back to his home town of Newmarket, Suffolk, England, but returned to Waterloo, Canada, in 2000.
Other Mathematicians born in England
A Poster of William Tutte

References (show)

  1. W T Tutte, Graph theory as I have known it (Oxford University Press, New York, 1998).
  2. W T Tutte, Graph theory (Reading, MA, 1984).
  3. N Biggs, Professor W T Tutte, Mathematician and Bletchley code-breaker (The Independent, 9 May 2002).
  4. C St J A Nash-Williams, A note on some of Professor Tutte's mathematical work, Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977 (New York-London, 1979), xxv--xxviii.
  5. Obituary of William T Tutte (The Times, 8 May, 2002).
  6. Professor Bill Tutte (The Telegraph, 9 May 2002).
  7. Papers and books by W T Tutte, in Graph theory and related topics, Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977 (New York-London, 1979), xxix-xxxii.
  8. W T Tutte, FISH and I, in Coding theory and cryptography, Annapolis, MD, 1998 (Berlin, 2000), 9-17. https://uwaterloo.ca/combinatorics-and-optimization/sites/ca.combinatorics-and-optimization/files/uploads/files/corr98-39.pdf
  9. C A B Smith, Early reminiscences, in Graph theory and related topics, in Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977 (New York-London, 1979), xix-xxi.
  10. D van der Vat, William Tutte (The Guardian, 10 May 2002).
  11. D Younger, Obituary of William T Tutte (Kitchener-Waterloo Record).

Additional Resources (show)

Honours (show)

Cross-references (show)

Written by J J O'Connor and E F Robertson
Last Update October 2003
  翻译：