William Thomas Tutte OC FRS FRSC (/tʌt/; 14 May 1917 – 2 May 2002) was an English and Canadian code breaker and mathematician.

The high-level, strategic nature of the intelligence obtained from Tutte's crucial breakthrough, in the bulk decrypting of Lorenz-enciphered messages specifically, contributed greatly, and perhaps even decisively, to the defeat of Nazi Germany.

[7] "Tutte advanced graph theory from a subject with one text (D. Kőnig's) toward its present extremely active state.

He was the younger son of William John Tutte (1873–1944), an estate gardener, and Annie (née Newell; 1881–1956), a housekeeper.

[4] In 1927, when he was ten, Tutte won a scholarship to the Cambridge and County High School for Boys.

In 1935 he won a scholarship to study natural sciences at Trinity College, Cambridge, where he specialized in chemistry and graduated with first-class honours in 1938.

Intelligence information had revealed that the Germans called the wireless teleprinter transmission systems "Sägefisch" ('sawfish').

The nickname Tunny (tunafish) was used for the first non-Morse link, and it was subsequently used for the Lorenz SZ machines and the traffic that they enciphered.

Nothing was known about the mechanism of enciphering other than that messages were preceded by a 12-letter indicator, which implied a 12-wheel rotor cipher machine.

Tutte played a pivotal role in achieving this, and it was not until shortly before the Allied victory in Europe in 1945, that Bletchley Park acquired a Tunny Lorenz cipher machine.

This allowed John Tiltman, Bletchley Park's veteran and remarkably gifted cryptanalyst, to deduce that it was a Vernam cipher which uses the Exclusive Or (XOR) function (symbolised by "⊕"), and to extract the two messages and hence obtain the obscuring key.

Recognising that the prime factors of this number are 2, 7 and 41, he tried again with a period of 41 and "got a rectangle of dots and crosses that was replete with repetitions".

Over the following two months, Tutte and other members of the Research Section worked out the complete logical structure of the machine, with its set of wheels bearing cams that could either be in a position (raised) that added x to the stream of key characters, or in the alternative position that added in •.

[18] Diagnosing the functioning of the Tunny machine in this way was a truly remarkable cryptanalytical achievement which, in the citation for Tutte's induction as an Officer of the Order of Canada, was described as "one of the greatest intellectual feats of World War II".

While on secondment to the Research Section in July 1942, Alan Turing worked out that the XOR combination of the values of successive characters in a stream of ciphertext and key emphasised any departures from a uniform distribution.

The resultant stream (symbolised by the Greek letter "delta" Δ) was called the difference because XOR is the same as modulo 2 subtraction.

[10]Tutte exploited this amplification of non-uniformity in the differenced values [nb 2] and by November 1942 had produced a way of discovering wheel starting points of the Tunny machine which became known as the "Statistical Method".

[21] The essence of this method was to find the initial settings of the chi component of the key by exhaustively trying all positions of its combination with the ciphertext, and looking for evidence of the non-uniformity that reflected the characteristics of the original plaintext.

The first machine was dubbed Heath Robinson, but the much faster Colossus computer, developed by Tommy Flowers and using algorithms written by Tutte and his colleagues, soon took over for breaking codes.

Tutte completed a doctorate in mathematics from Cambridge in 1948 under the supervision of Shaun Wylie, who had also worked at Bletchley Park on Tunny.

[26] The same year, invited by Harold Scott MacDonald Coxeter, he accepted a position at the University of Toronto.

Tutte was instrumental in helping to found the Department of Combinatorics and Optimization at the University of Waterloo.

The first major advances in matroid theory were made by Tutte in his 1948 Cambridge PhD thesis which formed the basis of an important sequence of papers published over the next two decades.

In addition to using peripheral cycles to prove that the Kuratowski graphs are non-planar, Tutte proved that every simple 3-connected graph can be drawn with all its faces convex, and devised an algorithm which constructs the plane drawing by solving a linear system.

Tutte's algorithm makes use of the barycentric mappings of the peripheral circuits of a simple 3-connected graph.

[28] The findings published in this paper have proved to be of much significance because the algorithms that Tutte developed have become popular planar graph drawing methods.

One of the reasons for which Tutte's embedding is popular is that the necessary computations that are carried out by his algorithms are simple and guarantee a one-to-one correspondence of a graph and its embedding onto the Euclidean plane, which is of importance when parameterising a three-dimensional mesh to the plane in geometric modelling.

"[29] Tutte was mainly responsible for developing the theory of enumeration of planar graphs, which has close links with chromatic and dichromatic polynomials.

This work involved some highly innovative techniques of his own invention, requiring considerable manipulative dexterity in handling power series (whose coefficients count appropriate kinds of graphs) and the functions arising as their sums, as well as geometrical dexterity in extracting these power series from the graph-theoretic situation.

[36] In September 2014, Tutte was celebrated in his hometown of Newmarket, England, with the unveiling of a sculpture, after a local newspaper started a campaign to honour his memory.