Maps, Maidens and Molecules

Maps, Maidens and Molecules: The world of Victorian combinatorics

Robin Wilson

This talk on Victorian combinatorics combines my interests in the history of British mathematics particularly during the Victorian period - and in combinatorics. The word 'Victorian' is straightforward: most of the events I'll be talking about occurred in Britain in the period of Queen Victoria's reign. But what about 'combinatorics'? The word is clearly related to 'combinations', and it refers to the area of mathematics concerned with combining, arranging and counting various things, as you'll see. Much of the development of combinatorics in the nineteenth century took place in Victorian Britain, often by eccentric amateur mathematicians (frequently, clergymen, lawyers and military gentlemen) who found such problems appealing; for example, in Thomas Pynchon's book Gravity's Rainbow, there's an elderly character called Brigadier Pudding, of whom it is said: he was, like many military gentlemen of his generation, fascinated by combinatorial mathematics. For today, I've chosen four typical (but varied) topics to illustrate Victorian combinatorics, and here are some of the people you'll be getting to know in the next hour. Incidentally, this talk can be taken on various levels, so although I'll need to get technical from time to time, don't worry if you don't follow all the mathematical details; just hang on and wait for the more historical parts.

I've called the first topic 'triple systems', and I'd like to start by introducing you to the annual Lady's and Gentleman's Diary: designed principally for the amusement and instruction of students in mathematics, comprising many useful and entertaining particulars, interesting to all persons engaged in that delightful pursuit. In 1844, its editor, the Revd. Wesley Woolhouse, himself a keen amateur mathematician, presented Prize Question No. 1733 for his readers to solve: Determine the number of combinations that can be made out of n symbols, p symbols in each; with this limitation, that no combination of q symbols, which may appear in any one of them shall be repeated in any other. Don't worry if you don't understand this - many of the attempted solutions showed that its solvers didn't understand it either. In fact, no-one managed to produce a satisfactory answer, and so in 1846 Wesley Woolhouse made it simpler by choosing p = 3 and q = 2. The problem then becomes: How many triads can be made out of n symbols, so that no pair of symbols shall be comprised more than once amongst them?

As you can see, it's a problem about arranging things: we take a number of symbols and we're asked to arrange them into 'triads', or 'triples', in such a way that a particular condition is satisfied. Here's an example. We've taken our 7 symbols to be the numbers 1 - 7, and arranged them vertically into triples, as shown below: 1234567 2345671 4567123 The condition that has to be satisfied is that no pair of numbers may occur together more than once - here, and from now on, each pair appears exactly once. For example, the numbers 2 and 3 appear together in the second triple, while the numbers 3 and 7 appear together in the final triple, and the same is true for any two of the numbers that you choose. Such an arrangement of numbers is now usually called a Steiner triple system, after the Swiss mathematician Jakob Steiner, but Steiner did nothing on them and the credit should rightly go to a Lancashire clergyman, the Revd. Thomas Penyngton Kirkman, who made substantial contributions to the subject, as you'll see. Kirkman was the rector of the tiny parish of Croft-with-Southworth, near Warrington. His parochial duties were not demanding, and left him a lot of time to have seven children and do a lot of mathematics, becoming a Fellow of the Royal Society in the process.

Here are two triple systems - the one we had before for n = 7, with seven triples, and one for n = 9, with twelve triples. Again, note that any pair of numbers appears in exactly one triple - for example, in the second system, the pair 3 and 8 appear together in the eighth triple. 1234567 2345671 4567123 111122233347 245645645658 379898787969 Such triple systems are used in agriculture, in the design of experiments. Suppose that you wish to compare seven varieties of wheat. If your fields are not large enough for you to plant all seven types of wheat in each field, you can plant varieties 1, 2 and 4 in the first field, varieties 2, 3 and 5 in the second, and so on. With the above arrangement, you can directly compare each pair of varieties in one of the seven fields.

Notice, by the way, that this first system is easy to construct, since from the first triple, consisting of 1, 2 and 4, you can then obtain each successive triple by adding 1 to each number, replacing 7 by 1 whenever you need to; so, once you've found your starting triple, the rest follows. Such systems are called cyclic systems, and we'll see them again later; they've even been used in music theory, where each triple represents a chord of three notes and each chord after the first is obtained from the previous one by transposition. When do triple systems exist? They certainly exist when n is 7 or 9, but for which other values? In a ground-breaking paper of 1847, Kirkman showed, by a simple counting argument, that triple systems can occur only when n, the total number of symbols, is one of the numbers in the sequence 7, 9, 13, 15, 19, 21, 25, . . . - these numbers are all 1 or 3 more than a multiple of 6; indeed, you can see that the total number n must be odd because the number 1 appears with all the other numbers in pairs. Kirkman also showed - and this was much more difficult - that for each such number one can actually construct such a triple system, and he gave an explicit construction for doing so.

Before I introduce the 'maidens' in the title of this talk, I'd like to look again at the system with n = 9. 147|123|123|123 258|456|645|564 369|789|897|978 Here I've rearranged the twelve triples in such a way that the system splits into four parts with all the numbers from 1 to 9 appearing in each part. In the context of comparing varieties of wheat, you can think of each part as representing a season: in the first season, you plant three fields with varieties 1, 2 and 3 for the first; 4, 5 and 6 for the second; and 7, 8 and 9 for the third; in the next season you plant them with varieties 1, 4 and 7; 2, 5 and 8; 3, 6 and 9; and so on for the remaining two seasons. After four seasons, you will have succeeded in comparing each pair of varieties exactly once. Such a division into seasons can happen only when n is divisible by 3, which means that n must be 3 more than a multiple of 6. This includes the case n = 9, and also n = 15, as we now see. One of the entertaining features of the Lady's and Gentleman's Diary was that it always contained a number of queries sent by the readers, and 1850 was no exception. In that year, there were queries by Mr Lugg on the origin of April Fools' Day, by the Revd. Hope on the three sons of Noah, by Mr Herdson on the saltiness of the sea, and finally a query by the Revd. Thomas Pennington Kirkman: Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily, so that no two shall walk twice abreast. If there had been only 9 young ladies, we could have used the system above, with the four seasons now corresponding to four days: on the first day, 1 walks with 2 and 3, 4 walks with 5 and 6, and 7 walks with 8 and 9; on the second day, 1 walks with 4 and 7, and so on - and no two young ladies walk together more than once.

The problem for 15 young ladies is now known as the Kirkman schoolgirls problem: here's a solution of it. (OHP) Monday: 1-2-3; 4-5-6; 7-8-9; 10-11-12; 13-14-15 Tuesday: 1-4-7; 2-5-8; 3-12-15; 6-10-14; 9-11-13 Wednesday:1-10-13; 2-11-14; 3-6-9; 4-8-12; 5-7-15 Thursday:1-5-11; 2-6-12; 3-7-13; 4-9-14; 8-10-15 Friday:1-8-14; 2-9-15; 3-4-10; 6-7-11; 5-12-13 Saturday:1-6-15; 2-4-13; 3-8-11; 5-9-10; 7-12-14 Sunday:1-9-12; 2-7-10; 3-5-14; 6-8-13; 4-11-15 Notice that, as before, any two schoolgirls walk together exactly once; for example, schoolgirls 3 and 10 walk together on Friday. This question was more successful than the one in the 1844 Lady's and Gentleman's Diary. Here are the solutions that appeared in the 1851 Diary: one by Kirkman himself, and one obtained independently by Mr Bills of Newark, Mr Jones of Chester, Mr Wainman of Leeds, and Mr Levy of Hungerford; how they all came up with exactly the same solution, I have no idea. Incidentally, Kirkman says: 'This is the symmetrical and only possible solution', but he was wrong . . . Another symmetrical solution, different from Kirkman's, had been obtained in the previous year by the distinguished mathematician Arthur Cayley, shown here thinking about the problem; we'll be meeting Cayley again later on.

The first person to treat the fifteen schoolgirls problem in a systematic way, rather than by organised guesswork, was another Victorian clergyman, the Revd. Robert Anstice, who had studied mathematics as a student in Oxford; regrettably, no pictures of him have survived. Anstice's achievement was to find a cyclic solution. Here it is, with the 15 schoolgirls denoted by 0 - 6 in blue, 0 - 6 in red, and a separate symbol for infinity. Notice that once you have the arrangement for Monday, you can then obtain the arrangement for each successive day by adding 1, always following 6 by 0 and leaving infinity unchanged. Monday: 8-0-0; 1-2-3; 1-4-5; 3-5-6; 4-2-6 Tuesday: 8-1-1; 2-3-4; 2-5-6; 4-6-0; 5-3-0 Wednesday:8-2-2; 3-4-5; 3-6-0; 5-0-1; 6-4-1 Thursday:8-3-3; 4-5-6; 4-0-1; 6-1-2; 0-5-2 Friday:8-4-4; 5-6-0; 5-1-2; 0-2-3; 1-6-3 Saturday:8-5-5; 6-0-1; 6-2-3; 1-3-4; 2-0-4 Sunday:8-6-6; 0-1-2; 0-3-4; 2-4-5; 3-1-5 At this point we meet the brilliant but eccentric James Joseph Sylvester, whose chequered career, on both sides of the Atlantic, culminated in his becoming Savilian professor of geometry in Oxford at the age of 69.

Sylvester believed that he had originated the schoolgirls problem, and said so in his own inimitable but somewhat incomprehensible way: . . . in connexion with my researches in combinatorial aggregation . . . I had fallen upon the question of forming a heptatic aggregate of triadic synthemes comprising all duads to the base 15, which has since become so well known, and fluttered so many a gentle bosom, under the title of the fifteen schoolgirls' problem; and it is not improbable that the question . . . may have originated through channels which can no longer be traced in the oral communications made by myself to my fellow-undergraduates at the University of Cambridge. As you can imagine, Kirkman didn't think much of this priority claim, and replied: No man can doubt, after reading his words, that he was in possession of the property in question of the number 15 when he was an undergraduate at Cambridge. But the difficulty of tracing the origin of the puzzle . . . is considerably enhanced by the fact that, when I proposed the question in 1849, I had never had the pleasure of seeing either Cambridge or Professor Sylvester. After citing his own paper, Kirkman concluded: No other account of it has, so far as I know, been published in print except this guess of Prof. Sylvester's in 1861.

But Sylvester did devise an interesting extension of the schoolgirls problem. The total number of possible triples of fifteen schoolgirls is 455, which is 13 × 35, and Sylvester asked: Can we arrange all these 455 triples into 13 separate solutions to the problem? that is, can we arrange 13 weekly schedules so that each possible triple of schoolgirls appears just once in the quarter-year. Kirkman claimed a solution in 1850, but he was wrong - and surprisingly a correct solution was not to be found for over a hundred years, when R. Denniston of Cambridge constructed one in 1971. In the same year, the general problem of solving the schoolgirls problem for any larger number of schoolgirls - not just for 9 or 15, but also for 21, 27 and higher numbers - was solved by Dijen Ray-Chaudhuri and Rick Wilson. However, Sylvester's extension of the problem for these higher numbers still remains unsolved to this day. Poor Kirkman was unlucky. Not only is he not generally given credit for his fundamental contributions to triple systems - he also didn't get credit for inventing Hamiltonian cycles, as we now see.

It is here that we first meet Sir William Rowan Hamilton. He was a child prodigy, who knew Latin, Greek and Hebrew at the age of 5, and then learnt Turkish, Arabic, Hebrew, Sanskrit and various other languages by the age of 11. He became Astronomer Royal of Ireland while still an undergraduate, and was knighted at the age of 30. Before we come to Hamilton's work on polyhedra, let's first look at some examples. A polyhedron is a solid shape whose faces are polygons - triangles, squares, pentagons, etc.; for example, here you can see a cube (bounded by six square faces) and a dodecahedron (bounded by twelve pentagons). And here's a polyhedron whose faces are not all the same - some are squares and some are hexagons; it's called a truncated octahedron. The Victorians were interested in problems of the type that later came to be set in Cambridge Scholarship exams: An intelligent fly decides to visit all the corners of a cube, and then return to its starting point. What route should he take? Why an intelligent fly should want to visit all the corners of a cube, I don't know, but here's one such route, shown on a flattened cube - just follow the blue path. Similarly, we can find a cycle passing through all the vertices of a dodecahedron and returning to the starting point - again, just follow the blue path.

And we can do the same for the truncated octahedron - as shown on this model, which I'll pass round; incidentally, this particular cycle arose in connection with a problem in bell-ringing, but that's another story. Are there such cycles for all polyhedra? In 1855, Thomas Kirkman gave an example to show that for some polyhedra, the answer is 'no'. As he observed: if we cut in two the cell of a bee . . . we get a 13-acron [Kirkman's word for a polyhedron with 13 vertices] . . . The closed 13-gon cannot be drawn. To explain why this is, I've drawn the polyhedron so that each edge has a red end and a blue end - so any cycle has to alternate red and blue points - red, blue, red, blue, and so on - and so the number of red points and the number of blue points must be the same. But there are six red points and seven blue points, so it can't be done. However, as Kirkman pointed out, if we now join these two points, then we can draw the required cycle - it's the red path here.

In the following year, 1856, Hamilton became interested in drawing cycles on a dodecahedron - these arose out of some work that he was doing in algebra, called the icosian calculus. For reasons I won't go into, he was interested in looking at three symbols i, k and l satisfying the equations i2 = k3 = l5 = 1, where i, k and l are linked by the equation l = i × k. If we now write m = i × k2 (which is the same as l × k), we can obtain this lengthy expression here, which Hamilton then proceeded to interpret in terms of a cycle on a dodecahedron: you'll see why if you start here and think of l as turn right and m as turn left: right, right, right, left, left, left, right, left, . . . Hamilton was so proud of his icosian calculus that he converted it into a game called A Voyage Around the World, in which the twenty vertices are labelled with consonants B, C, D, . . . , Z, representing places (Brussels, Canton, Delhi, . . . , Zanzibar) and the object is to travel around the world and return to your starting point; one solution is to follow alphabetical order: BCDFGH . . . ZB. Hamilton proudly sold the game to a games manufacturer for £25 - which was a wise move as it didn't sell. Here are the instructions for his icosian game, containing various puzzles of the form: you are given five initial points, such as B, C, D, F, G; in how many ways can you complete the cycle? . . . and here's the game itself, in which twenty numbered pegs are to be placed into the twenty holes in cyclic order. Such was Sir William's importance and influence that these cycles are now called Hamiltonian cycles, rather than being more justly credited to Kirkman, who had preceded Hamilton by several months and who had also discussed cycles on general polyhedra - and not just on a dodecahedron.

For our third topic, we turn to trees - and here the two central figures are Arthur Cayley and James Joseph Sylvester, both of whom you've already met. Around 1850, Cayley couldn't obtain a professorship in Cambridge without taking holy orders, while many jobs were closed to Sylvester, who was Jewish. So they both worked as lawyers at Gray's Inn, near here, writing several hundred mathematical papers in their spare time and quickly establishing themselves as the greatest pure mathematicians in the country. In the 1850s, both Cayley and Sylvester became interested in tree structures. These are branching diagrams that contain no cycles - familiar examples include family trees (assuming no inter-marriage), river tributaries, and certain chemical molecules, such as alkanes (or paraffins). Earlier in the 1840s, trees had also been used by Gustav Kirchhoff in his investigations into currents in electrical networks.

Cayley's interest arose from a problem of Sylvester's on the differential calculus which led to the study of rooted trees. These are trees where everything branches down from one special vertex, called the root - don't ask me why mathematicians always put their roots at the top. Here's an 1859 paper of Cayley, in which he draws the small rooted trees with a given number of terminal vertices - the ones at the bottom; for example, there are just three rooted trees with three terminal vertices, and thirteen rooted trees with four. Cayley was primarily concerned with counting rooted trees - which he did by using a device, invented in the eighteenth century, called a generating function 1 + A1x + A2x2 + . . . , where An is the number of rooted trees with n branches; this has the great advantage that you need to consider only one expression at a time, instead of a whole string of numbers all at once. If we now slice off the root, we get several smaller rooted trees, and this leads to this equation - a recurrence relation from which each successive number Ai can be found iteratively: knowing A1 you can deduce A2; knowing A1 and A2 you can deduce A3; and so on. This gives the table of numbers shown below; for example, there are 48 rooted trees with six branches, and 719 rooted trees with nine branches.

Counting unrooted trees, where there is no special root-vertex, is much harder to do, but Cayley found a way of doing it - by starting at the middle of the tree and gradually working outwards. He obtained these numbers . . . - for example, there are 106 unrooted trees with nine branches. What was the purpose of all this? It was around this time, the 1850s and '60s, that the chemical theory of valency came to be sorted out, and Cayley's motivation for counting trees was to enable him to enumerate those chemical molecules (the paraffins, alcohols, etc.) that have a tree structure. Here's a list of Cayley's tree papers; as you can see, there are both mathematical and chemical papers - the mathematical ones are circled in red, and the chemical ones in green. James Joseph Sylvester was also interested in chemistry. He had been fascinated by the recent use of tree-like pictures to depict molecules, by the celebrated chemist Edward Frankland, and was convinced that there was a connection between such 'graphic formulae' and certain ideas from algebra. Indeed, in a paper in 1878, he really waxed eloquent: Chemistry has the same quickening and suggestive influence upon the algebraist as a visit to the Royal Academy, or the old masters may be supposed to have on a Browning or a Tennyson. Indeed it seems to me that an exact homology exists between painting and poetry on the one hand and modern chemistry and modern algebra on the other . . . Here are some of Sylvester's drawings from this paper - some are certainly chemical, while others are more related to algebra.

The motivation for all this arose from the fact that he had just been appointed as the first professor in mathematics at the newly-founded Johns Hopkins University in Baltimore, and he was faced with the problem of giving an inaugural lecture to a mixed audience. Indeed, in the same paper, which appeared in Volume 1 of the American Journal of Mathematics (which he'd just founded), he describes (in a single sentence) how he came across this supposed connection between chemistry and algebra: Casting about, as I lay in bed one night - can you imagine today's research papers containing such phrases? - to discover some means of conveying an intelligible conception of the objects of modern algebra to a mixed society, mainly composed of physicists, chemists and biologists, interspersed only with a few mathematicians - and so he continues - I was agreeably surprised to find, of a sudden, distinctly pictured on my mental retina a chemico-graphical image - and so on - the sentence still has some way to go.

As a footnote, if you're familiar with graph theory, you may be interested to know that when Sylvester summarised the results of this paper in Nature in 1878, he described the link between chemical atoms and algebraic expressions called binary quantics, saying: Every invariant and covariant thus becomes expressible by a graph. This is the first-ever appearance of the word graph, in the sense of graph theory. Before we leave Sylvester, I should remark that studying him can be very frustrating because his letters are so difficult to read. In fact, I can't resist showing you this extract from this letter to the German mathematician Felix Klein: Dear Professor Klein, I find some difficulty in making out some of the words in your highly esteemed letter, and would take it as a great favor if you could write a little more clearly for my behalf as I am not very familiar with German handwriting.

No talk about Victorian combinatorics would be complete without a mention of map colouring, and in particular the celebrated four-colour problem. In October 1852 Francis Guthrie, a former student at University College, London, was colouring a map of England, and noticed that he needed only four colours to colour it so that neighbouring counties were differently coloured. Is this true for all maps?, he wondered. His brother Frederick then asked his teacher, Augustus De Morgan, Professor of Mathematics at University College, who immediately became fascinated with the problem and communicated it to his friends. Here's the first appearance of the problem - a letter from De Morgan to Sir William Rowan Hamilton, saying: A student of mine asked me today to give him a reason for a fact which I did not know was a fact - and do not yet. He says that if a figure be anyhow divided and the compartments differently coloured so that figures with any portion of common boundary line are differently coloured - four colours may be wanted but not more . . . Query: cannot a necessity for five or more be invented.

De Morgan also wrote about the problem to the philosopher William Whewell, Master of Trinity College, Cambridge. In fact, it was in the middle of an unsigned book review (actually by De Morgan) of Whewell's Philosophy of Discovery that the problem first appeared in print, in a very strange passage: . . . Now, it must have been always known to map-colourers that four different colours are enough. Let the counties come cranking in, as Hotspur says, with as many and as odd convolutions as the designer chooses to give them; let them go in and out and roundabout in such a manner that it would be quite absurd in the Queen's writ to tell the sheriff that A. B. could run up and down in his bailiwick: still, four colours will be enough to make all requisite distinction . . . - so that's perfectly clear. A few years after De Morgan's death, our friend Arthur Cayley raised the question again at a meeting of the London Mathematical Society, and in the following year, in 1879, a 'proof' that four colours are sufficient was given by Alfred Kempe, a London barrister who had studied at Cambridge with Cayley, and who later became treasurer of the Royal Society. Kempe's proof was essentially as follows. It's a bit technical, but doesn't last long!

We assume that the result is false, so that there are maps that need more than four colours. Of these, let's take such a map with the smallest possible number of colours that cannot be four-coloured - so this map M cannot be four-coloured, but any map with fewer countries can be. Using a result called Euler's polyhedron formula (which I won't go into), it's easy to show that every map has a country with at most five neighbours, such as a triangle, square or pentagon. Let's look at these in turn. If the map has a triangle, shrink it to a point. There are then fewer countries, so by our assumption we can four-colour the resulting map. Now put the triangle back again - it's surrounded by three countries, taking up only three colours, so there's a spare colour to colour the triangle - giving the required contradiction. If, now, there's a square, we follow Kempe and look at just two of the colours - say, the red-green part of the map. Are the reds and greens up here connected to the reds and greens down here? Let's look at the two cases, which you can see here. In Case 1 they're not connected, whereas in Case 2 they are connected. So in Case 1, the reds and greens up here are separated from those down here, so we can interchange the reds and greens up here without affecting the reds and greens down here (red becomes green, green becomes red, and so on). So this country becomes green, and so is this one, so we can colour the square red. In Case 2, interchanging the colours leaves us no better off than before - but now we look at the blues and oranges here, and here. The ones here are separated from those here by the red-green chain, so we can interchange the blues and oranges here without affecting the ones here, and the square can then be coloured blue.

Finally, if there's a pentagon, Kempe claimed that you can do two simultaneous interchanges of colour to get rid of the two reds. This gives just three colours around the pentagon, so the colouring can again be completed. This completes the proof. Kempe's proof was widely accepted - by Cayley, Sylvester and others - so it was a great surprise, eleven years later, when Percy Heawood of Durham wrote a paper in which he pointed out a fundamental error in Kempe's proof. Heawood had first learned about the problem in 1880, while an undergraduate in Oxford, and he became hooked - writing several papers on the subject, his last appearing when he was aged 90. Like several others in this talk, he was somewhat eccentric - for example, he used to set his watch just once a year, and the story goes that a friend once asked him the time, and said 'You're two hours fast.' 'No', replied Heawood, doing the necessary calculation, 'I'm ten hours slow.' Heawood's paper was a bombshell, as no-one was able to patch up the mistake. Heawood himself managed to salvage enough from Kempe's proof to show that all maps can be coloured with five colours - itself, quite a worthwhile result - and he also tried to extend the result to other mathematical surfaces, as we'll see in a moment.

But where did Kempe go wrong? Recall that when dealing with the pentagon, Kempe tried to carry out two colour interchanges at once. Heawood constructed this map to show why this is not allowable. So let's look at Heawood's example and see just where Kempe went wrong. Here's Heawood's map, with one pentagonal country still to be coloured, as in Kempe's proof. As you've just seen, it can certainly be four-coloured, but Heawood's object was to use it to show that we cannot do two colour interchanges at once, as Kempe had tried to do. First, let's look at this blue country and this yellow one: they're connected by a blue-yellow chain, so this red and this green are separated. So we can interchange the reds and green up here without affecting those down here - and we get this new colouring . . . and that's perfectly all right. We can do that colour-interchange without difficulty. Now let's look at this blue country and this green one: they're connected by a blue-green chain, so this red and this yellow are separated. So we can interchange the reds and yellows down here without affecting those up here - and we get this new colouring . . . and that's perfectly all right, too. But if we try to do both interchanges of colour at the same time, then we get this - two reds coming together. So that's where Kempe went wrong.

The error proved very difficult to patch up - in fact, it took a further 86 years to do so - but in fact the eventual proof by Kenneth Appel and Wolfgang Haken used two important ideas that can be traced back to Kempe, which I'll just outline briefly. The first is that of an unavoidable set of countries. Since every map contains at worst a pentagon, we say that these configurations are unavoidable - in any map you can't avoid them. As we've seen, we can deal with the first three, but the pentagon causes trouble, so we replace it by something else. In fact, we can show that any map without a triangle or square must have, not only a pentagon, but either two adjacent pentagons or a pentagon joined to a hexagon - so we get a new unavoidable set - and we can then go on replacing these by more and more complicated arrangements, giving us further unavoidable sets. We've also seen that these configurations are reducible, in the sense that any four-colouring of the rest of the map can be extended to include them, but that we couldn't deal with the pentagon. The American George Birkhoff showed in 1913 that this configuration of four adjacent pentagons is reducible, and since then, many thousands of reducible configurations have been found.

In order to prove that four colours are sufficient, we need to find an unavoidable set of reducible configurations - unavoidable means that every map must include at least one of them, and reducible means that whichever one it is, we can complete the colouring of the map. After a long struggle, making massive use of a computer, Kenneth Appel and Wolfgang Haken in 1976 found an unavoidable set of 1936 reducible configurations, thereby proving the four-colour theorem. To conclude this talk, I'd like to return very briefly to Heawood's 1890 paper, and to his attempted extension of the four-colour problem to other surfaces. Using a map projection, we can see that colouring maps on the plane is the same as colouring maps on a sphere (such as a globe) - but what about colouring maps on other mathematical surfaces, such as a torus, or rubber ring? Here the magic number turns out to be be 7 - using Euler's polyhedron formula, it's easy to prove that seven colours are always enough, and here's a torus map that actually needs all seven colours. If you now introduce more holes (such as in a pretzel), you'll need more colours. In fact, as Heawood showed, if the number of holes is g, then you need this number of colours: take 1 + 48g, take the square root, add 7, divide by 2, and then take the integer part of the result - just what you'd have expected!

For example, if g = 1 (the torus has one hole), then 1 + 48g is 49, its square root is 7, and we get 7 for the number of colours, as before. What Heawood failed to show is that there are always maps that need this number of colours - and that took a further 78 years to prove. Proving the Heawood conjecture, as it came to be known, turned out to involve twelve completely separate cases. By 1967 ten of these cases had been settled - mainly by the German mathematician Gerhard Ringel and the American Ted Youngs. Ringel then had a sabbatical, so he went to California to work with Youngs on the remaining two cases, and in a couple of months they succeeded in finishing the proof. Great rejoicing! Later that year, Ringel was driving up the California expressway when he was stopped by a traffic cop for speeding. The cop looked at his driving licence, and said 'Ringel, eh - are you the one who solved the Heawood conjecture?' Ringel, very surprised, said 'yes'. It turned out that the traffic cop's son was in Professor Youngs' calculus class, and the result was that Ringel got let off with a warning - and if that doesn't show the uses of map colouring, I don't know what does!

© Robin Wilson, 2002