If William Tutte is remembered at all by architects, it is for his contribution to solving the problem of Squaring the Square . (Tutte 1958) A solution using Graph Theory and Kirchhoff’s Laws for electrical flow in wires that was subsequently used in Philip Steadman’s The Automatic Generation of Minimum Standard House Plans. (Steadman 1970)

This last, ultimately failed enterprise is explained in some detail here.

Bill Tutte died in 2002 and his obituaries, like this from the Guardian, reveal that he also had a wider influence on world events.

The Squaring the Square problem had been worked on at Cambridge by Bill Tutte, Leonard Brooks, Arthur Stone and Cedric Smith. They had met in 1936 and formed  the self-styled Important Members of the Trinity Mathematical Society. Collectively they published papers under the pseudonym Blanche Descartes, a name created from their first names; Bill, Leonard, Arthur, and Cedric to form BLAnChe and Descartes giving a play on carte blanche.

Code Breaking

At the outbreak of the Second World War, Tutte was invited to join the  Government Code and Cipher School at Bletchley Park where he initially worked on Italian Naval Codes, before moving onto the Lorenz cipher. Enigma coding machines were used by all branches of the Wehrmacht, but the Lorenz code was only used for the top-secret, high-level traffic of the German general staff.

The breaking of the Enigma code, worked on by Alan Turing, benefited from earlier work by Polish mathematicians passed onto the French and then the British. Lorenz on the other hand had to be broken from scratch. The Enigma machines had 3 or 4 rotors or code wheels but the never seen Lorenz machine had an unknown number of rotors, eventually established as 12.

Bill Tutte’s relation to Lorenz has been described as being equivalent to Alan Turing’s relation to Enigma.

At first, each Lorenz coded message had to laboriously broken by hand, but Max Newman suggested that Turing’s pre-war idea of a computing machine could be applied to the problem. But the first machine called Robinson, named after cartoonist Heath Robinson’s amazingly ramshackle machines, proved unreliable.

Discussions between Newman, Turing, Tutte and Tommy Flowers, a Post Office telephone engineer, led to an electronic version of Robinson. This was Colossus; the first semi-programmable computer.

The application of Colossus to Lorenz messages provided continuing access to high grade intelligence, particularly that the D-day landing deceptions had been successful; ensuring that the Normandy landings could be carried out with a high degree of confidence.

Four Colour Theorem

A coloured map can be represented as a planar graph if the coloured regions of the map are replaced by same coloured vertices in the graph, and vertices are joined by an edge in the graph if their corresponding regions in the map share an edge.

In fact the planar graph is a dual of the map, and the map can be generated from the graph and vice versa. Both map and graph obey Euler’s formula for networks f + v -e = 1, or regions + vertices – edges = 1. In the examples above 7 regions + 11 vertices – 17 edges = 1 for the map and 10 regions + 8 vertices – 17 edges = 1 for the graph.

The planar graph is therefore an exact equivalent of the map and the Four Colour Conjecture can be expressed as seeing if the vertices of the graph can be coloured with 4 colours so that no 2 adjacent vertices have the same colour.

More importantly planar graphs lend themselves to computer manipulation.

In 1976 Appel and Haken announced a ‘Proof’ of the Four Colour Conjecture that required the unavoidable computer testing of the reducibility of 1,936 graph configurations. (Appel and Haken 1977)

These tests were done by different software and computers, but the idea of  a computer checked proof remained problematic, particularly as the method was complicated and checking by hand so tedious that no one had tried it.

In 1996 Robertson, Sanders, Seymour and Thomas announced a simpler proof, that still required computer checking but was more amenable to verification by manual means. Their paper bears the following dedication (Robertson et al 1996)

DEDICATED TO PROFESSOR W.T.TUTTE ON THE OCCASION

OF HIS EIGHTIETH BIRTHDAY

Bibliography

Appel, K., Haken, W. and Koch, J.  1977 Every Planar Map is Four Colorable. I: Discharging. Illinois J. Math. 21, 429-490

Appel, K. and Haken, W. 1977 Every Planar Map is Four-Colorable, II: Reducibility. Illinois J. Math. 21, 491-567.

Brooks, R.L., Smith, C.A.B., Stone, A.H. and Tutte, W.T., 1940 The Dissection of Rectangles into Squares Duke Mathematical Journal, vol. 7, pages 312-40

Robertson, N.; Sanders, D. P.; Seymour, P. D.; and Thomas, R. A. 1996 New Proof of the Four Colour Theorem. Electron. Res. Announc. Amer. Math. Soc. 2, 17-25.

Steadman, P., 1970. The Automatic Generation of Minimum Standard House Plans Working Paper 23 University of Cambridge Land Use and Built Form Studies

Tutte, W. T., 1958. Squaring the Square from ‘Mathematical Games’ column, Scientific American Nov 1958.