Connecting the Dots: Milestones in Graph Theory

Connecting the Dots: Milestones in Graph Theory

Professor Robin Wilson

13th June 2023

Introduction

Today I’ll be talking about graph theory – but these graphs aren’t the curves like y = x2 that you see in mathematics books but are diagrams that depict connections between things – such as the London Underground network of stations linked by rails, or chemical molecules with carbon and hydrogen atoms linked by chemical bonds. The nature of the connections doesn’t matter – for example, the Underground map doesn’t show the lengths of the connecting rails, or whether they’re curved or straight – all that matters is which stations are connected to which.

For the past 50 years I’ve been interested in the history of graph theory. In the 1970s I collaborated on Graph Theory 1736–1936, in which we presented the subject’s first two centuries by means of a number of original articles, translated into English where necessary. Then, earlier this year, Princeton University Press published Graph Theory in America, which arose out of the Ph.D. thesis of an Open University student of mine and describes in particular the American aspects of the story between 1876 and 1976. And just last week, I and two colleagues from America and Denmark submitted another manuscript, which presents the 20th-century story up to the present day. So today’s lecture is partly a book launch – past, present and future!

So how did graph theory arise? As the preface of our first book observed:

“The origins of graph theory are humble, even frivolous. Whereas many branches of mathematics were motivated by fundamental problems of calculation, motion and measurement, the problems which led to the development of graph theory were often little more than puzzles, designed to test the ingenuity rather than to stimulate the imagination. But despite the apparent triviality of such puzzles, they captured the interest of mathematicians, with the result that graph theory has become a subject rich in theoretical results of a surprising variety and depth.”

Indeed, graph theory today pervades every area that involves connections – road, rail and communications networks, operations research, neural nets, computing, social nets, chemistry, and much else besides.

Today I’ll focus on six of these historic puzzles, describing how they arose, bringing their stories up to date, and introducing you to some major problems with which graph theorists are involved. These puzzles are the Königsberg bridges problem, the knight’s-tour problem, the utilities problem, the ‘Good Will Hunting’ problem, the minimum connector problem, and the four-colour problem.

But first, some terminology, most of which is pretty straightforward. A graph consists of some points (usually called vertices or nodes) which are joined in pairs by lines (called edges or arcs). If all the vertices are joined, we have a complete graph; for example, the complete graph K5 has five vertices joined by ten edges. For any vertex, the number of emerging edges is its degree, and if all the degrees are all the same, the graph is called regular. A graph which is regular of degree 3 is sometimes called a cubic graph. Most graphs have cycles, and a graph with no cycles is called a tree. Finally, a bipartite graph is a graph in which every cycle has an even number of edges. Notice that a tree is also a bipartite graph, because it has no cycles at all.

Let’s now return to the problems.

Königsberg Bridges Problem

The first problem is well known, and concerns the medieval city of Königsberg, now known as Kaliningrad. The city has four parts which are connected by seven bridges (see Fig. 1). The problem is to find a walk which crosses all seven bridges once only and ends up at the start. The citizens soon found themselves unable to do so – but is this really the case, or is there such a route?

It was Leonhard Euler, the most prolific mathematician of all time, who solved the problem in 1735, introducing his published solution with the following words:

“In addition to that branch of geometry, which is concerned with magnitudes, there’s another branch, previously almost unknown, which Leibniz first mentioned, calling it the geometry of position. Concerned only with the determination of position and its properties, it does not involve measurements, nor calculations made with them. It hasn’t yet been satisfactorily determined what problems are relevant to this geometry, or what methods should be used in solving them. So when a problem was recently mentioned, I had no doubt that it was concerned with the geometry of position . . .”

Euler’s solution involved a counting argument. For a successful walk, whenever we enter a region, we must be able to leave it again, thereby using two bridges – so the total number of bridges around each region must be a sum of 2s – that is, an even number. But for Königsberg the numbers of bridges are 5 around region A , 3 for B, 3 for C, and 3 for D. These numbers are all odd, so the walk cannot be done – the problem has no solution.

But actually, if exactly two of the numbers had turned out to be odd, then we can still solve the problem as long as we start in one of the odd regions and end in the other. Euler illustrated this in an example with six regions, in which the numbers of bridges around the regions are 8 for region A, 4 for B and C, 3 for D, 5 for E and 6 for F, and we so can complete a walk as long as we start and end in the regions D and E.

What has all this to do with graphs? The way we now solve such problems is to draw a graph whose vertices correspond to the regions, whose edges correspond to the bridges, and where the number of bridges around a region becomes the degree of the corresponding vertex. The problem is then to draw the graph in one continuous pen-stroke without repeating any line, and the condition for a solution is that the number of vertices of odd degree is either 0 (when we end where we started) or 2. So for the Königsberg problem, we get the graph in Fig. 2, and the degrees are again 5, 3, 3, 3, which are all odd so there’s no solution.

Regrettably, it's often claimed that this was how Euler originally solved the problem – by drawing this graph. But he didn’t. The earliest appearance of the Königsberg graph seems to have been in a popular book of mathematical recreations written in 1892 – more than 150 years after Euler originally solved the problem.

But such diagram-tracing puzzles became quite popular in the 19th century, and here are three examples. We can certainly trace Fig. 3 in one continuous pen-stroke, because the vertex-degrees are all even (they’re all 6). The diagram in Fig. 4 has eight vertices of odd degree 3, and each walk uses two of these, so four walks are necessary. And the diagram in Fig. 5 – introduced in 1847 by Johann Listing, the person who introduced the word “topology” to mathematics – has just two vertices of odd degree (one at each end), and so this diagram can be drawn in just one pen-stroke as long as we start at one end and finish at the other.

Knight’s-tour Problem

Let’s now turn to our second problem – known to chess enthusiasts as the knight’s-tour problem. Many centuries old, this problem asks whether a knight can visit all the 64 squares of a chessboard by knight’s moves and return to its starting point. (A knight always moves two squares in one direction and one square in a perpendicular direction.)

To get some idea of what this problem entails and its link with graph theory, let’s look at the simpler example of a 4 × 4 chessboard. We can then draw a graph with 16 vertices corresponding to the 16 squares, where the edges correspond to knight’s moves (see Fig. 6). Our problem is then to find a cyclic tour that visits each vertex just once and returns to the start. But this is impossible, because to pick up the two white corner squares we must include four edges which already complete a cycle which prevents us from visiting any other squares.

For the 25 squares of a 5 × 5 chessboard, we notice that a knight always moves from a black square to a white one (and vice versa), so any cyclic path must alternate black–white–black–white, etc. It follows that the number of black squares and white squares must be the same, which is impossible when there are 25 squares altogether. And similarly, there are no knight’s tours on a 7 × 7 chessboard, or a 9 × 9 one, or for any chessboard with an odd number of squares.

Turning now to the original 8 × 8 chessboard, we meet Euler again, who became interested in this problem around 1759, and produced several valid solutions. Fig 7 shows a particularly interesting solution. If we call the first visited square 1, the next one 2, and so on, we get the pattern of numbers on the right which is notable for the fact that if we add up all the numbers in each row or column, we get the same sum, 260. Euler’s also found a knight’s tour for a 10 × 10 chessboard, with the numbers from 1 to 100 linked by knight’s moves.

Some years ago, a Cambridge scholarship question began with the words: “An intelligent fly wishes to visit all the six corners of a cube . . .”. Fig. 8 shows the graph which represents a cube, and the solid lines give a route that the fly can take. So unlike the bridges problem where we go over every edge (inevitably passing through some vertices several times), here we must visit every vertex just once (inevitably omitting some edges). It’s like the difference between an explorer who explores every path and a traveller who visits every city.

And we can ask the same question of other polyhedral shapes. For a dodecahedron, we can follow the path shown in Fig. 9. This last problem also has an interesting history. In the 1850s, in connections with his research in algebra, the Irish mathematician Sir William Rowan Hamilton asked for such routes on a dodecahedron, subject to certain specified conditions. He also turned the problem into a game – the Icosian game – where the 20 vertices correspond to the 20 consonants of the alphabet, and we seek ‘A Voyage Round the World’, from B (Brussels) and C (Canton) to Z (Zanzibar). He then sold the game to a games manufacturer for £25 – which was a wise move as it didn’t sell!

Because of Hamilton’s fame and influence, graphs with a route through all the vertices are now called Hamiltonian – but they should really be named after the Revd Thomas Kirkman, a Lancashire country vicar whose parish duties left him time for mathematics and having seven children. Kirkman was writing about cycles on polyhedra before Hamilton did, and not only for a dodecahedron.

Kirkman also gave example of polyhedra with no such cycles, such as the one in Fig. 10, which is produced (apparently) ‘if we cut in two the cell of a bee’. To see why this has no Hamiltonian cycle, we note that the graph is bipartite, and so we can colour its vertices red and blue with each edge having a red end and a blue one. Now any cycle must alternate red–blue–red–blue–etc., and so there must be equal numbers of vertices of each colour. But there are 6 red vertices and 7 blue ones, so no cycle can be found.

We conclude this section with a more recent result. In 1880, the question had been raised as to whether every cubic polyhedron (that is, one with three faces meeting at each corner) has a Hamiltonian cycle, as do the cube and dodecahedron. Kirkman simply couldn’t decide, declaring that this problem ‘mocks alike at doubt and proof’. It then took over 60 years before the question was answered – by Bill Tutte, a major figure in graph theory who had earlier shortened World War II by decoding Adolf Hitler’s Tunny codes at Bletchley Park. In 1946 Tutte published an example of a polyhedron with 46 vertices which has no Hamiltonian cycle, and since then other (smaller) examples have been discovered.

Utilities problem

Our third problem concerns three unfriendly neighbours, Mr Angry, Mr Beastly and Mr Cross, who wish to link their houses to the three utilities gas, water and electricity in such a way that no connections cross. The origins of this problem aren’t known, but it was certainly presented by the American puzzler Sam Loyd around 1900. It is quite simple to insert eight of the links from the houses to the utilities without any edges crossing, but can one fill in all nine?

In graph theory terms we’re asking whether the graph K3,3, the bipartite graph with three vertices in each part, is planar – that is, can it be redrawn in the plane without any edges crossing (see Fig. 11)? To see why this cannot be done, we notice that six of the edges form a hexagon (from G to B to W to C to E to A and back to G). We must now try to add in the other three edges. But if any one of them lies inside the hexagon, then the other two must be outside it and must therefore cross – and similarly if justmone of them lies outside the hexagon. So in each case the task is impossible – this graph cannot be drawn in the plane, and the utilities problem has no solution.

So when is a given graph planar? Some graphs can indeed be unscrambled so as to avoid any crossings, but (as we’ve just seen) the utilities graph cannot be, and nor can the complete graph K5 with five vertices, as you can easily check. But in 1930 the Polish mathematician Kasimir Kuratowski proved the remarkable result that that these are essentially the only obstacles to planarity, in the sense that a graph can be drawn in the plane without crossings if and only if it does not contain either of these two graphs.

But we can say more. In 1750, Euler (yet again!) observed that, for any polyhedron,

(the number of faces) + (the number of vertices) = (the number of edges) + 2

– a fact that no-one seems to have observed before. For example, a cube has 6 faces, 8 vertices and 12 edges, and 6 + 8 = 12 + 2, and a dodecahedron has 12 faces, 20 vertices and 30 edges, and 12 + 20 = 30 + 2. And the formula works equally well for graphs drawn without crossings in the plane.

We can use Euler’s formula to prove results about polyhedra. The polyhedron in Fig. 12 is called a truncated icosahedron – or by some people a football – and is made up from pentagons and hexagons with just three faces meeting at each vertex. More complicated examples of such polyhedra are the chemical molecules known as fullerines, or buckyballs. These molecules are all made up from just pentagons and hexagons with three meeting at each point, and their names come from Buckminster Fuller, the American architect who used the idea when constructing his geodesic domes for various exhibitions and world fairs.

What’s interesting is that, however many hexagons there are – and this can vary – there can be only 12 pentagons. To prove this we use Euler’s formula.

First we count the faces. If there are p pentagons and h hexagons, then F, the total number of faces, is p + h.

Next we count the edges around the faces. Each pentagon has 5 edges, giving us 5p edges in total, and similarly the hexagons give us 6h edges. Adding these gives a total of 5p + 6h edges – but actually we’ve counted each edge twice because it appears on two faces, so we get the equation 2E = 5p + 6h.

And similarly, if we count the three edges at each vertex, we get a total of 3V edges. But again, each edge meets two vertices and is counted twice, so 3V = 2E, which equals 5p + 6v.

We now have expressions for F, V and E, and we can put these into Euler’s formula, F + V = E + 2. This gives an equation in which the h-terms all cancel, leaving an equation involving only p, the number of pentagons. Solving this gives p = 12, so however many hexagons there are, than can be only 12 pentagons.

Good Will Hunting Problem

We turn now to our fourth problem, which I call the Good Will Hunting problem. In this film, the janitor, played by Matt Damon, encounters in a Massachusetts Institute of Technology corridor what the film describes as “an extremely difficult problem in functional analysis which took two years to solve”. It asks: How many homeomorphically irreducible trees are there with 10 vertices? But actually, it’s a simple problem in graph theory which I’ve often set to my students.

As I mentioned earlier, a tree is a graph that has no cycles; Fig 13 shows the six different trees with 6 vertices. But how many trees have 10 vertices, or 100 vertices?

Some chemical molecules also have a tree structure, such as the alkanes (or paraffins). Fig. 14 shows two different molecules with the same chemical formula C4H10, each with four carbon atoms linked to ten hydrogen ones. Called isomers, these arise from the two different trees with four vertices formed by the carbon atoms. But how many isomers are there with (say) 10 carbon atoms? Such problems were studied in the 19th century by two English mathematicians, Arthur Cayley and James Joseph Sylvester.

Returning to the Good Will Hunting problem, ‘homeomorphically irreducible trees’ are simply trees with no vertices of degree 2 – so four of those in Fig. 13 don’t qualify as they all have vertices of degree 2; the other two have no such vertices and are homeomorphically irreducible. I’ll leave it to you to find all the ones with 10 vertices, as the janitor did.

Another result of Cayley involved the counting of ‘labelled trees’. Although there are just two trees with 4 vertices, we get many more different ones if we label the vertices. Cayley asserted that for trees with n vertices, the number of labelled trees, is exactly nn–2, a delightfully simple result to state. So for four vertices there are 42 = 16 labelled trees, and for n = 5, the number is 53 = 125. But Cayley proved his result only for n = 6, where there are 64 = 1296 such trees, and it took some years before the result was fully proved.

Minimum Connector Problem

Cayley’s result is also relevant to our fifth problem. Here we wish to interconnect several towns or cities by links, which may be canals, railway lines, or air routes, etc., but we wish the total connection cost to be as small as possible. We certainly cannot include any cycles in our connections, because removing any edge from a cycle would lower the total cost. So what we seek is a tree that connects all the cities.

Fig. 15 shows a simple example with five cities, A to E, all linked by connections, where the numbers might be the distance between them, or the cost of construction. But, by Cayley’s result, there are 53 = 125 trees linking these cities, so which one gives the lowest possible cost? Can we find out without checking all 125 possible trees?

It turns out that we can – and with a reliable method that’s simple to apply. It’s called a greedy algorithm, because at each stage we’re ‘greedy’ and select the cheapest link that’s available – as long as we don’t create a cycle by doing so.

So here, we first choose the cheapest link AE, which has cost 2, and then the link EC with cost 3. But we cannot now select the next cheapest link (AC with cost 4), because this would create the cycle AECA – so instead we choose the next cheapest link, which is CB with cost 5. But now we’re stuck again, because if we choose either AB or EB, both with cost 6, we get a cycle. So instead we choose the next cheapest link, which is ED with cost 7. This gives us the tree in Fig. 16 with total cost 2 + 3 + 5 + 7 = 17, which is better than the trees we had before.

It turns out that the greedy algorithm always produced a tree with minimum possible cost.

A problem that sounds somewhat similar, but which is very different in practice, is the ‘travelling salesman problem’, which dates back to the 19th century. Here, a salesman wishes to make a circular tour of some cities, while keeping the total travelling cost to a minimum. This time, we’re not seeking a minimum-cost tree, but a minimum cost Hamiltonian cycle through all the vertices.

Here are the same five cities, and using trial and error I found the optimum route in Fig. 17, with total cost 26. But unlike the previous problem where there was an easy-to-apply method (the greedy algorithm) for solving the problem, none is known for this one – although some heuristic methods are known which give approximations to the best route.

Colouring Maps

We’ll conclude with two problems on the colouring of maps. In 1852, it was found that four colours will colour the counties of England so that neighbouring counties are coloured differently, and the question arose as to whether all maps can be so coloured. Fig 18 shows a 4-coloured map. The connection with graphs arises because instead of colouring the regions of the map, we can colour their capitals. This gives a colouring of the vertices of a graph in which vertices joined by an edge are coloured differently.

The four-colour problem has a long and fascinating history which I’ve presented here on an earlier occasion, and which is on the college’s website. Suffice it to say that the problem took 124 years to be solved, and that a proof that four colours suffice was finally presented in 1976 by Kenneth Appel and Wolfgang Haken, two mathematicians at the University of Illinois, who used the graph formulation and reduced the problem to the consideration of 1936 cases which they then examined by computer.

Their proof was the first major mathematical proof to be solved in this way, and caused much controversy among mathematicians who considered a proof to be invalid if it cannot be checked by hand. But others acclaimed their success, and I later wrote a book about its history and solution.

I’d like to conclude with a related colouring problem. Colouring maps on a plane is equivalent to colouring maps on a sphere or globe, so how many colours are needed for maps on other surfaces, such as a torus (or bagel).

This question was raised in 1890 by the English mathematician Percy Heawood, who showed that every torus map can be coloured with 7 colours, and gave an example of such a colouring (see Fig. 19). And for doughnut-like surfaces with g holes, he showed that the number of colours needed is given by the formula [1/2 (7 + √(48g + 1)], where [.] means ‘take the integer part’. So for the torus where g = 1, we get the answer 7 (as expected), and for the double torus where g = 2, we need 8 colours.

But Heawood failed to prove that, for all surfaces, there are maps that need all these colours, as we did for the seven colours on a torus. Seeking a proof of this became known as the Heawood conjecture, and it took a further 78 years to find. A proof was completed in 1968 by the German Gerhard Ringel and the American J.W.T. Youngs, and split into twelve separate cases. By 1967, nine of these cases had been completed, and Ringel travelled to California to work with Youngs on the last three. After several months they succeeded, and there was great rejoicing in the graph theory world.

© Professor Wilson 2023

References and Further Reading

1. N.L. Biggs, E.K. Lloyd, and R.J. Wilson, Graph Theory 1736–1936, Oxford University Press, 1976; paperback edn., 1998.

2. Robin Wilson, John J. Watkins and David J. Parks, Graph Theory in America: The First Hundred Years, Princeton University Press, 2023.

3. Lowell Beineke, Bjarne Toft and Robin Wilson: Milestones in Graph Theory: A Century of Progress (to appear).

4. Robin Wilson, Four Colors Suffice, Princeton University Press, 2014.