Now, today I'll be talking about graph theory, but these graphs are not the curves, like y equals X cube that you see in mass books, but the diagrams that depict connections between things such as the London underground network of stations linked by rails or chemical molecules, uh, as shown here with carbons and hydrogen atoms linked by chemical bonds. The nature of the connections doesn't matter. The, 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 it's exactly 50 years. This year, since I became interested in the history of graph theory, which is what I'll be talking about today, in the 1970s, I collaborated on the book on the left Graph Theory 1736 to 1936. Not a very exciting title in which we pre, we presented the subjects 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. This arose outta the doctoral thesis of an open university student of mine, and describes in particular, the American aspect of the story between 1876 and 1976. But we do include all the other, the European work as well as that. And just last week, I and two colleagues, uh, from America and Denmark submitted the manuscript on the right, which presents the 20th century story up to the present day. So today's lecture is partly a book launch, a book launch, past, present, and future. So how did graph theory arise as the preface of our first book observed? The, 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, in, in theoretical results of the surprising variety and depth. And indeed graph theory Today, perv pervades every area that involves connections, road rail and communication networks, operations research, neural nets, computing, social networks, chemistry, and much else besides so, because graph theory arose outta puzzles largely today, I'm going to focus on six of these historic puzzles describing how they arose, bringing their stories up to date, and introducing you to some of the major problems with which graph theorists are involved. Uh, some of these will be familiar to you. There's the Kosberg bridges problem, the knight's to problem in chess, the utilities or Gas, water, water and electricity problem, A problem arising from goodwill hunting, uh, the minimum connector problem, uh, and, and the map color problems. But first, let me introduce some technology, which I, some terminology, which I'll need, uh, most of which is, is pretty straightforward. So in this talk, a graph consists of, of some points usually called vertices or nodes, which are joined in pairs by lines called edges or arcs. So on the left is a graph with five vertices, uh, joined by seven edges. If all the vertices are joined. We have a complete graph, so such as the second one, which is the complete graph, K five. For any vertex, the number of emerging edges is its degree. So the first graph has two vertices of degree two, that one, and that one, it has, uh, two vertices of degree three, this one and that one, and of vertex of degree four. And of all the degrees are the same. The graph is called regular. So the complete graph K five is a regular graph of degree four. There are four edges out of each vertex. The third graph is also regular, this time of degree three, and we sometimes call it a cubic graph. Most of the graphs have cycles where you go around and return to your starting point. So you can see in the first graph, for example, there are three triangles. Uh, a couple of Quadra quadrilaterals. There's one, there's another one, uh, and, uh, the outside Pentagon. But a graph with no cycles is called a tree, like a family tree. So on the right, the graph on the right is a tree, which is well known for its bark. Uh, I've been telling that joke for 50 years. And the, um, finally, a bipartite graph is a graph in which every cycle has an even number of edges. For example, a third graph there is bipartite, because you can see some quadrilaterals. You can see, uh, some, some hexagons like this one here, uh, and the outside octagon, of course, but there are no, um, there are no triangles or pentagons, for example. And notice that tree, the tree is also a bipartite graph, got all cycles there. Well, it has no cycles at all, let alone odd ones. So let's now return to the problems. The first of these is well known, I'm sure, to many of you, and concerns the medieval city of Koenigsberg, now known as Coleen grad. As you can see, there are four parts of the city. 1, 2, 3, 4 joined by, all connected by seven bridges. And the problem that the ci the citizens had was to find a walk, which crosses all seven bridges once only, and if possible ends up where we started. So you could start here up and then, and then down here, and then, uh, and then, uh, whoops, I've left out that one. So let's start with that one. That one here. Oh, I've left out that one. So it, it, it's not awfully easy to do that. Uh, and in fact, the, the citizens soon found themselves unable to do so. But is this really the case or, or is there such a root? And at this stage, we welcome Leonard oer, the most prolific mathematician of, of all time, um, who has actually lectured here at Gresham College, uh, in a certain period costume. Uh, he solved the problem, uh, 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 liveness first mentioned calling it the geometry of position. This is concerned only With the determination of position in its properties. It does not involve measurements nor calculations made with them. It Hasn't yet been satisfactory to determine what problems are, 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. So it's a geometrical problem, but one which doesn't involve any ideas of measurement or length or angle or anything like that. Uh, and the problem he's referring to, of course, is the kosberg problem. So how did oiler solve it? So he first redrew the map of Koenigsberg, uh, as you can see up here, to show the connections more clearly. And you notice that all ideas of of distance have now gone. The important thing is the connection between the four land areas, uh, and the connections formed by the seven bridges. And he then used a counting argument for a, excuse me, for a successful walk. Whenever you enter a region, you must be able to leave it, uh, which means, um, that you use two bridges. So the total number of bridges around each region must be a sum of twos. That is an even number. But here, the number of bridges around each area are 5, 3, 3 and three Five round region A, three for B, three for C, and three for D. And these numbers are all odd. So the war cannot be done. The Koenigsberg bridges 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 you start in one of the odd regions and end in the other. And oiler illustrated this in this example below. This also appears in his paper of 1736, uh, here illustrated with this. And here the number of bridges around the areas are for A, you've got eight, uh, for B and C, you've got four for D, five for E, and six for F. And so you can complete a walk as long as you start and end in the regions D. So if you want to go over each of the bridges, you start here and you can cross all and end up there or the other way around. What has all this to do with graphs? Well, the way we solve such problems now is to draw a graph whose vertices correspond to the regions whose edges correspond to the bridges, And where the number of bridges around the region becomes the degree of the corresponding vertex. The problem is then to, and so you get the picture down below. The problem is then to draw the graph in one continuous pen stroke. So you've got to draw the graph without repeating any line. And the condition for solution is now that the number of vertices of odd degree is either zero, in which case you end up where you started, or two, in which case you start in one, uh, odd, odd degree and end in the other. So for the cunnings problem, we get this graph here, and the degrees are, again, 5 5, 5, 3 33, which are all odd. There are four of them. So there's no solution. Now, regrettably, it's often claimed that this was how oiler originally solved the problem. Even just a couple of couple of months ago, I saw an article which said that oiler solved the kosberg problem by Troy, the graph. He did not draw that graph. And as far as I can find out, the earliest appearance of this Kosberg graph seems to have been in a popular book of mathematical recreations, written as late as 1892, more than 150 years after oiler originally so solved the problem. And indeed, when the Quadrennial International Congress of mathematicians was held, uh, in 2 20 14 in Korea, the Congress issued this postage stamp of the, of the Kosberg of Kosberg, the Kosberg, uh, map with, with the graph. And it says at the top, Leonard Oyer, this was the International Congress of mathematicians, and they got their history completely wrong. What a shame. They never read our books. But such diagram tracing puzzles became, became quite popular in the 19th century. And here are three examples. The, We can certainly trace the first one in one continuous pen stroke because the vertex degrees are all, even, they're all six. One way is go around the outside, then jump one each time, 0, 2, 4, 6, 1, 3, 5, 0, and then jump two at a time and so on. And, uh, so that's one way of doing that for the picture on the right. Can we draw that in one continuous stroke, or two or three, if you count the number of vertices of odd degree, you'll see there are eight of them. There are eight vertices of degree three. Now, each, each, each walk will take up two of them. So it means you're gonna need at least four walks, and then you find you can do it with four. You start here, go all the way around, and then you add these three separate ones. So four is the answer to that question. How about the lower one? This is a nice picture. It was introduced in 1847, uh, by Johan Bene Benedict listing. Uh, he was a mathematician, particularly interested in, in the mathematics of optics. And he was the person to introduced the word topology to mathematics. Topology is often described as rubber sheet geometry. If you, if you, if you draw a picture on a bit of rubber and you stretch it, of course you lose all the ideas of length and angle and everything, but some properties are still preserved and what properties are preserved, that's what the subject of topology is all about. Uh, and it was listing who introduced that, that, that, that word, first of all, in a letter he wrote in 1838. And then in, in, in an article he wrote, uh, in 1847, where he presented, uh, the last two of these diagram diagram tracing puzzles, uh, and, um, uh, and pointed out that this you can do in one continuous stroke. You can do it in one pen stroke because this has got degree five, that's got degree five, all the others have got even degree. So, uh, you know that you can do it as long as you start at one end and end at the other. Doesn't tell you how to do it, but you know that it can be done. Let's now turn to our second problem known to chest enthusiasts as the night tour knight's tour problem. And this problem, many centuries old ask whether a knight can visit all the 64 squares of a chessboard by knight's moves and return to its starting point, and knight's moves. You can recall that a night always moves two squares in one direction and one square in a perpendicular direction. So it can go to any of the squares marked here, two in one direction, and one in a perpendicular direction. Well, before embarking on that problem in generality, let's see what it entails, uh, and what it's linked with graph theory. And so I'm gonna look at the simpler example of a four by four chess board. The one down here, first of all, you can draw a graph with 16 in vertices with the vertices corresponding to squares of the chess board, uh, and the edges correspond to knight's moves. So there is a link with graph theory, and the idea is you've got to trace this whole, this whole picture passing through every vertex. So our problem in this case is to find a cyclic tour, which visits each vertex exactly once and returns to the, to the start. But this is impossible because if you To to, to pick up this vertex, you are going to need to have these two edges to pick up this one. You're going to need to have these two edges, and that already completes the cycle. And so you've left out a whole lot of the squares. So, so you're stuck. And similarly, for a five by five one, to pick up all the, these four corners here, um, you're gonna have to include these, these edges, these ones, these ones and these ones. And so, uh, already you've, you've completed your cycle and there's still a lot of squares you haven't visited. So that one doesn't work work either. But for the five by five, in fact, there's an even simpler way of, of, of seeing, uh, that you can't do it because a knight always moves from a black square to a white square or a white square to a black square. And so any cyclic path must alternate black, white, black, white, black, white, all the way around. And what does that mean? That tells you that the number of black squares must be the same as the number of white squares. If the number of black squares and white squares are the same, that's impossible when there are 25 squares altogether. And so similarly, there are no night tour on a seven by seven, seven chess board, or a nine by nine one, or for any chess board with an odd number of squares. So turning now back to the original H by H chessboard, we meet oiler again. Oiler seems to have been the first mathematician to study the problem mathematically. Uh, there were two papers that came out in, around that time. He oiler wrote one in 1759, and there's another, uh, paper by someone called Vander Mond, who's known in mathematics for something called the Vanderman determinant. Vander Mon wrote six papers, none of which mentions anything about the so-called Vander mon determinant, but there we are. Um, but Oyer got interested and, and he, he started the problem. And first of all, he came up with this solution, 1, 2, 3, 4. The trouble is that 1 64 don't match up, but he did actually work a bit harder, and he did find some solutions, uh, uh, to this problem. And here is a solution. This is a particularly interesting one here. You can see the night starts here and goes round here. And if you count the squares as you go, one to two, to three, to four to five, and so on, um, then, uh, you get this pattern of numbers here. And what's interesting about this particular pattern of numbers is not only does it give you a night's tour, but it's actually what we call semi magic square. Because if you add up all the numbers in each, in each row, you get 260. And if you add up all the numbers in each column, you get 260. Uh, and uh, now if it were a real magic square, if you added all the numbers on two diagonals, then that would also be 260, and it's not. And so the question is, is there a solution where you can actually get the diagonals adding up as well? And, um, it was only very recently, I think, that there's a computer search which showed that there is no, unfortunately, there is no solution where you can get the diagonals working as well. But even so that, that's pretty remarkable, I think. And on the top right, you can see, uh, Oilers solution for a 10 by 10 chess board with the numbers from one to one to a hundred, uh, all linked up by night's moves again, 1, 2, 3, 4, and so on. Well, these problems are visiting all the vertices, uh, crop up in different situations. Some years ago, a Cambridge scholarship question began with the words, an intelligent fly wishes to visit all the six corners of a cube. Anything more stupid for a fly to wish to do. Seems hard to imagine. Uh, but anyway, uh, so here's a cube. Now, you can actually draw the graph of it. If you sort of flatten it, you get this picture here. And, uh, and so where does the fly go? The, the fly starts here and goes around there. And so I once gave this lecture using an overhead projector, actually, uh, and, uh, unknown to, I couldn't see it, but the audience could. There was a fly there. And just when I started, it started walking along the path. And so the audience from fits of laughter, and I didn't know why, but they were so, uh, that, uh, is how you do it for a cube. Uh, So the solid lines gives us a route, the flag and tape. But unlike the bridges problem where we go over every edge, inevitably passing through some vertices several times here, we're visiting every vertex just once inevitably omitting some edges, the dashed ones there. So it's like the difference between an explorer who explores every path, and a traveler who wishes to visit every city. And we can ask the same question of other poly polyhedral shapes as well. The second one is not octahedron eight faces. And if you squash it flat, you get this picture here, and it's quite easy to see the, to find a path which goes through all, all the vertices. And you can ask the same question also for a dodecahedron. Uh, uh, uh, the dodecahedrons got 12 pentagonal faces. And, and, uh, if you squash it flat, you get this picture. And the red, the red path tells you, uh, a path, gives you a path through all the vertices. And that's a particularly interesting one historically, uh, um, because in the 1850s, in connection with some researchers in algebra, the Irish mathematician, so William Rowan Hamilton asked for such such route on a do deh, uh, subject to certain conditions. For example, can you find, and you can easily trace this bbc, you just followed consonants, bbc, d, fg, and so on. But supposing you're saying you're told that you have to start J E L D B. How many ways can you complete it? There are a number of, of questions that he posed there, uh, which he, he found quite fun, um, and in fact, so much fun. He found it as he turned the problem into a game called the Ian Game, um, where the 20 vertices correspond to the 20 consonants of an, of the alphabet, and we seek a voyage round round the world. So if you start B, C, and so on, B was Brussels, C was Canton. And you, the idea was to, uh, is to get to Z, which was Zanzibar. Uh, and he sold this game to a games manufacturer for 25 pounds, which was a wise move as it didn't sell<laugh>. I once went to the Irish Academy, where, where they actually have, have, have an original, they're, they're all solid ones, but the best ones are the flat ones here. And, and I went in and uh, and there are lots of people there studying sixth century Irish manuscripts. Some of them looked as though they'd been there since the sixth century. And there I was, there I was with all my pegs, putting things in, in having great fun, getting some very funny looks. Now because of Hamilton's fame and influence, graft, Twitch have a root through all the vertices are now called Hamiltonian, but they should really be named after the Reverend Thomas Pennington Kirkman, Lancaster Country Vicar, whose parish duties left him lots of time for mathematics. He became a fellow of the royal society and all. He also had seven, seven children for Kirkman's writing about cycles on Polyhedra in general before Hamilton did. Uh, as I say, not only for for Dodecahedron. So Kirkman has was there about six months before Hamilton and more generality, but Hamilton's so famous that they're now still named Hamiltonian instead of named Arthur Kirkman. But Kirkman also gave examples of Polyhedra, which don't have any such cycles, such as the one here. And, and his paper on this one here, um, starts off, um, if we cut in into the cell of a B, then you get this particular pattern here, which I'm prepared to believe, um, to see why it has no Hamiltonian cycle. We notice that the graph is bi apartheid. All of the cycles have even length, which means that we can color its versus these red and blue, so that each edge has a red end and a blue end, which I've done here. So I've covered each, each edge has a red end and a blue end. And now we have the same example that we had before, cuz any cycle must alternate red, blue, red blue, red, blue, and so on. So there must be the same number of vertices of each color, but there are six red vertices there and seven blue ones. So no cycle can be found. So as I said, that's somewhat similar to the argument we used for the five by five chess board. So talking about Hamiltonian graphs before moving on, let me conclude with a slightly more recent result, the, because in 1880 the question had been raised as to whether every cubic polyhedron, that's one with three faces, meeting at each verdict, each corner, whether every cubic polyhedron has a Hamiltonian cycle as, as does the C and has does the do dodecahedron? Well, well, Kirkman thought about this in 1884 and couldn't decide whether it does or not and say it mocks a life alike doubt and proof. So that didn't help much. And it actually took over 60 years before the problem was finally settled by Bill Tutt, who is a major figure, uh, in this country's history, uh, um, in Bletchley Park. He was the mainly the person who, who decoded the, uh, Hitler's UHT codes at Ley Park. Uh, and, uh, but he later became a major figure in graph theory. And in 1946, tar wrote a paper which actually follows from some of the graph theories he was doing at Blakeley Park. Uh, he, he, he published an example of, of this polyhedron here. If you think of wrapping it round, uh, you actually get a polyhedron there, that's the flattened version. And, and that's got 46 verse, uh, vertices, and it has no Hamiltonian cycle. So after all that time, he found a a counter example. He answered the question, uh, with the answer no. And since then, a few other examples have been, some smaller examples have, have been discovered. So moving on to our third, uh, third problem, um, is it arises from a utilities problem in which three unfriendly neighbors, a, B, and C, whom I usually call Mr. Angry, Mr. Beasley and Mr. Cross, they wi they wish to connect their houses to the three utilities of gas, water, and electricity in such a way because they're unfriendly that none of the connections was cross. Now, the origins of the problem aren't known, although it certainly presented by the American puzzler, Sam Lloyd, who wrote puzzle books in America around 1900. And on the right is an attempted solution, which where I've tried to insert the, the nine, the nine links. So here, here you can see them, except I haven't quite, I haven't linked B to water. So how do I put, can I put the, the, the ninth one in or can I rearrange it so you can, you can do the ninth one. Uh, and so that, that's a big question. Can, can you draw, uh, uh, the three, uh, the three utilities, three houses, can you link them up with nine edges? So in graph theory, in graph theory terms, you've got this picture here, and we want to redraw this so that none of the, some, none of the edges cross cross, okay? And so what we're asking a graph is plainer if you can draw it in the plane without any crossings. So the question is, is, is this planer? So nothing could be much plainer than that. So we can ask, uh, we can ask this question, and, and, and the answer is no to see why you notice that six of the, uh, Six of them form a hexagon. Uh, you can go G, b, w, c, e, A and back to G. So, so you can draw those as a hexagon. And then you've still got this, the other three edges to, to fit in. So let's take this horizontal one. If that goes inside, then both of these must go outside so they don't cross it, but then they'll cross each other. So that's no good. And if you put this one outside, uh, then these two will have to be inside, but they, they'll still cross. So it, in either way, there's no way of doing it. The graph cannot be drawn in, the graph can cannot be drawn in the plane. And the utilities problem has no solution. So when in general is a given graph planer, and this is answered actually, uh, by several people at the same time. Uh, but the important, uh, person that I want to mention is a famous Polish topologist called Kowski, whom I met once. Actually, it was very interesting. Uh, so some graphs such as the, uh, such as this, these are planar cuz you can, you can redraw it, you can pull these things out and that's planar. But This one is not planar. And in the same way you can show that this one is not planer, that's quite an easy, easy art thing to do as well. So these two are not planar. The important result of kowsky is these are essentially the only ones. Cuz if you have a graph which is not plainer, then it must contain at least one of these two. Uh, and that's quite a remarkable result. Interestingly, Ky himself, uh, said that, uh, uh, he was assuming that was the only one that didn't work, and it was only when he came to the end of the proof that that suddenly popped up. Uh, and, uh, so he had to deal with that as well. But that's a very famous result in graph theory that it, uh, which describes completely when a graph is plainer or not, that these are the only obstacles. But we can say more about Plano graphs. Uh, and this is oiler again, uh, in 1750, oiler observed that for any polyhedron, the number of faces plus the number of vertices is the number of edges plus two. For example, this has six faces, eight vertices, 12 edges, and six plus eight is 12 plus two. Uh, For a dodecahedron, uh, there are 12 faces. There are 20 vertices. As we, as we saw, 30 ages. 12 plus 20 is 30 plus two. And here's a great run by costi dodecahedron. It's, uh, it's called in the trade. And you can see immediately that it has 62 faces, 120 vertices in 180 edges, and 62 plus 120 is 180 plus two. Uh, so it doesn't have to be regular. You can have have d different types of faces and, and, and, and the, the results still works. Um, so this was an important result. How did it arise? Well, let me show you the place it first appeared. Uh, Oyer, um, had been in St. Petersburg for a time. He then moved to Berlin in 1741. And in 1750 he wrote to his friend and colleague, Christian Goldbar, um, who is still in, in, in, in St. Petersburg, and who is famous, uh, for an unpro conjecture on prime numbers. Some of you'll know of Goldbar conjecture. Uh, and the formula, uh, o's formula for is, is right here. H plus S equals A plus two. Here H is heat dry. La uh, uh, Latin, um, heat dry for, uh, Latin for faces. S uh, talks about solid angles. The solid angle is if you like, a, a verdict. And, uh, and a is acqui, which is edge. Interestingly, oiler was, I mean, lots of people had looked at, at poly heater in the past. The Greek, the ancient Greeks had johans. Kepler had a lot in, in around in the 16 hundreds, but no one has ever looked at edges before, uh, or, or tried to count them. And it was, and so it was oil introduced the word acqui for ages. And so that's that age. So this is the first appearance of, of oil's formula and further down the, the page of the letter. And he, he takes a particular example and he, and he checks the, that it works for that. So, uh, I thought you might like to see that. And the former also works for grass drawing the plane as shown here. Here are the five regular solids, some of which we've already met. And if you draw their graphs, as I say, flatten 'em out, uh, these are, these are their graphs, and you can check Oilers formula for each of them. Nope, that works. And we can actually use Oilers formula to prove results about Polyhedra. Now this polyhedron here, uh, is called a truncated, uh, truncated icosahedron, or some people call it a football. Um, and as you can see, it's made up from pentagons and hexagons with just three faces meeting at each point. But more complicated examples of of, of polyhedra made, of pentagons and hexagons are the chemical molecules known as rines or bucky balls. And here's, here's one is C 60, which is essentially the same as this. Uh, but there are lots more complicated ones all made with penins and hexagons. As I say, they're called followings and bucky balls. Um, and their name comes from Buckminster Fuller. Uh, the American architect who used the idea when constructing his geodetic go domes that you can see below for various exhibitions and world faires. Um, and so what's interesting, they say that every mass lecture should have both a joke and a theorem, and you should be able to tell the difference between them. So here is, uh, here, here is, um, a calculation, right? What's interesting is that for any of these polyhedra, uh, where you've got penins and hexagons with three meeting at a point, there can be lots and lots of different numbers of hexagons, but they're always exactly 12 pentagons. Uh, and we can prove that using oil, oil is formula. So first of all, so I'm gonna assume I got a soccer ball with p pentagons and h hexagons. So total number of faces is obviously P plus h. Now I'm gonna count the ages around the faces. So there, there are p pentagons and five edges round. So it gives you five p edges. Round, round the pentagons, There are h hexagons and six edges round. So you're gonna get six H edges around there. So the total number of edges is, is, is, is five people, plus, plus plus six, eight, it seems, oh, but each edge has got two faces. So each, if you do this, you're gonna count each edge twice, once for this face and once for this face. So in fact, you get two E and not are not, are not e and suddenly you can count the three edges at each vertex. Uh, and you get the similar thing, three V. But if you count the three edges, then, then each edge has got two ends. So you're going to get two E again. And so you're going to going to get five p plus two, six H again. So, so you've got F, e, and V and you can now substitute them into one's formula. So here's F uh, V is a third of this, uh, is e which is a half of this plus two. So there's that formula there. Well, fortunately, h plus two hs and three hs, they cancel. And that leaves a a, an equation which you can solve to give p equals 12. So there must be exactly 12 pentagons. So we, we, we've proved the result. And you can also use oil, that's formula. In a similar way, I decided not to include it in this, but you can try it for yourself to prove that there are exactly five regular solids, um, the ones I showed you earlier there. So let's now move to our fourth problem, which I call the goodwill hunting problem. And in this film, if you saw it, you'll notice the janitor played by Matt Damon is walking down the corridor in the mass Massachusetts of institute or techno, Massachusetts Institute of Technology, mit, uh, he and he, he discovers a mathematics problem on the board. Now, the film describes this particular problem as an extremely difficult one, which the mathematicians at MIT had worked on for two years and finally managed to solve it, uh, an exceedingly difficult problem in functional analysis. Well, don't worry about what functional analysis, but it, it's actually a very, very simple problem in graph theory to draw all the homomorphic irreducible trees with 10 vertices. And I'll explain what that means in a minute. But basically that's an easy problem to solve. I've given it often to my students, um, and they will get it right first time, even if MIT professors take two years to do it. So let's look at trees. This is a tree in case you've never seen these things before. Um, and a tree is a graph that has no cycles. So below is a family tree, which is indeed a tree, as long as there's no incest or anything like that. Uh, and uh, and then down below, uh, here are some chemical trees. Now these chemical trees have got four carbons, which form a, a carbon tree with, with, with, with eight, with, uh, 10 hydrogens around them. Uh, these are called kines or, or paraffins. So lots of paraphernalia here. Uh, and uh, um, so here are two different molecules with the formula C four H 10. And there is no two different ones is because there are two trees with four vertices. Look at the carbons. You get this one and you get this one. And, uh, and so you get these two different chemical molecules with the same formula, but different structures, and they're called isomers. And you might say, well, how many isomers, how many are isomers are there with, with, with say, 10 carbon lessons? Here are all the trees with six vertices. There are six of them. So how many trees have 10 vertices? How many trees have a hundred vertices? These are mathematical problems which, uh, um, one might want to try and solve. And the particular one we're talking about, uh, a tree is polymorph irreducible. If it has no vertex of degree, two, well, these vertices of of degree. So that one's no good. This one's no good. This has got a verdict of degree two. That one's no good. That one's no good. But these are, okay. So there are two, um, homomorphic irreducible trees with six vertices, and there are so many a number with, with 10 vertices. And I'll leave that as an exercise for the reader. So you can, you can solve the Matt Damon m mit problem yourself, I'm sure without much difficulty. Um, oh, I should incidentally say that, um, problem, these counting problems were, were studied very much in the second half of the 19th century, in particular by two English mathematicians, Arthur Kaley and James Joseph Sylvester. Uh, they, they did a lot of work, very important pure mathematicians in this country. Uh, Sylvester also went in fact to America. Uh, and there's a whole chapter about him in this wonderful book here. Um, but there's another result of Kaylee, which is quite interesting, which involves counting label trees. Now, although they're just two trees with four vertices, if you start labeling them, I mean, here's, here's a, um, this is, these are all the same tree. They're just a path. And these are all, um, the other, the other tree. But if you label them dif in different ways, then you can actually see that there are 16 different, different possibilities, 16 ways of labeling, labeling this tree. I mean, I've drawn them in different ways, but you can see that this is, this is 2 1, 3, 4. There's 1, 2, 4, 3, 3, 1, 2, 4, 1, 3, 2. There are all different ways of labeling it. And so how many ways can you label, uh, a tree with, with four vertices? The answer 16 with five vertices is a hundred and twenty five six vertices is 1,296. Uh, Kayleigh came up with a formula that if, if the n vertices, then the number of labeled trees is n to the N minus two. So this is four squared, five cubed, six to the fourth, and so on. Unfortunately, Kaylee proves his result in detail only in the case n equals six, saying it's easy to see that proof works in general, which is not exactly a rigorous proof. Uh, and in fact it took some years, in fact not till 1918 when a German mathematician approved the result in general. And there's still, there are many proofs. Now we're now moving on to our fifth problem. And here we wish to connect several towns or cities by links, which may be canals, railway lines, or air route. But we wish the total connection cost to be as small as possible. So I want to choose some of these edges so that it remains linked up. But I want to do it in such a way that the total cost is as small as possible. So you certainly don't want to include a cycle, because if you include a cycle, you can take away any age and that automatically reduces the cost. So what we're looking for is a tree that goes through these five vertices. Well, we just seen there are 125 possible trees. Um, we don't want to go through 'em all. Let's look at a few. I mean, I could have taken this tree here. Oh, that has cost 23. Here's a, a better one. This has got 21. This is even better. This has got 20. Is that the best we can do? It would be nice to have a method, uh, for finding the shortest tree. We don't want to have to go through all, all, all the possibilities. And in fact, there is a method, and it's called the greedy algorithm. Because at each stage we are as greedy as we can be by choosing the smallest possible edge available. When I say the smallest possible edge available, I mean the smallest possible edge, as long as it doesn't create a cycle. So the first thing we do is we look, we'll take ae that's being greedy, that's cost two. Now let's take ec That's okay, but I can't now choose the edge four because that will create this cycle. So I, I ignore that one and I choose the next one that's there's five. Okay, so I've got this one, this one, and this one. I can't now choose this one, which is six. Cause that gives me a cycle. And I can't choose this one, which is six cause that, that cuz that that also, that gives me this cycle. So I've gotta choose the seven. So I've got this, oh, and I've, I've finished. So, so I've stopped. And that's has total cost, 17, which is better than any, any of the ones I had before. And the remarkable thing about the greedy algorithm, it always produces a tree with minimum possible cost. It may produce, um, if some of the costs are the same, it may produce different trees, but it always produces a solution to the problem. A tree with minimum cost. And if all these costs happen to be different, then in fact the answer's unique. There's just one, one solution. And this method, um, for finding minimum cost trees was introduced by check mathematicians in the 1920s. Subject was revised, was revived in America in the 1950s. A couple of important papers by kcal. It's sometimes called Krus Carl's algorithm. Uh, and, and someone called prim. And in Prims paper here is his solution for the 48 Coterm stent, uh, states. That's, in other words, not, not Alaskan, Hawaii, but the other 48 states. This is the minimum span, the minimum tree, uh, going through all of those, those capitals. Now interestingly, uh, that that's a problem which has a complete solution. Uh, but there's another problem which stands rather similar, but which is very different in practice. And this is the so-called traveling salesman problem. Um, where you, you've got a traveling salesman who visits, um, a number of cities selling graph theory books or something, uh, and, and they want to visit the cities and return to starting point, minimizing the total traveling cost. So this time we're not looking for a tree, we're looking for a Hamiltonian cycle, aren't we? So for example, we for this, the same exact we could take, we could go around the outside that could do, uh, 29, you can take this star pattern. That's 20 also 29. This is 28. Can you do any better? Well, I played around with it for a bit. This is the best one I could find. I think it's the, it's the optimum solution with, with total cost 26. But I had to do it by trial and error. There is, unlike the greedy ALG algorithm problem, there is no simple algorithm known. And anyone who could find one would be worth millions of pounds. So I can encourage you to do that over supper. Um, so unlike the other one that's easier to apply method, uh, but for this one, there are heuristic methods which will give you fairly good solutions, fairly good approximations to the answer. But there is no complete answer. And in fact, it was some time before the problem for the 48 states, w w was solved. And this apparently is the minimum cost, uh, for the capitals of the 48 states. So we come through our, our loss problem. Now, um, in fact, two problems on the coloring of maps in 1852, it was found that four colors, uh, are, uh, enough to color the counters of England so that neighboring counties are colored differently, okay? Um, and so the question arose as to whether all maps can be so colored. So here, for example, is, is a four coloring of the 48 American states. Uh, and on the left you can see why you, you can't get away with better than four. In general. Here you've got four neighboring coun, four neighboring regions. So each of them must be different from the other three. So you're gonna need have four colors there, there. And in fact, you might need four colors, even if you haven't got four mutually neighboring regions. As in this example here, the outside ring has got five. So you can't alternate in colors. You're gonna need three for the outside ring. They're all gonna have to be different from the middle one. So there's another one where you're gonna need four. And this example here occur occurs with Nevada. You've got the five states around form forming a ring with Nevada in the middle. So, um, so, and the connection with graphs, by the way, uh, I mean here's, here's a map of the states of, of, of, of Australia. Instead of coloring the the states, you might want to color the capitals and, and join them by, by edges when they're in, when they're neighboring. So you are really coloring if you like, the vertices of a graph. Uh, whereas instead of having neighboring states having different colors here, you've got joined vertices having different colors. So in fact, you can state it in the language of graphs and, and, and when certain problems are solved, this is the language that graph theories usually use. Uh, well, the, the history of the, of the four color problem I've lectured on here before, you can probably find it on the website. Uh, so I'm not gonna go through all that. I'm gonna cut through to the end, uh, o of, of it where it was finally solved. Uh, you can act, can you prove that all maps can be colored with four, with just four colors? This took 124 years to prove. And, and the argument is, is is quite complicated. Uh, it's not deep, but it's difficult. Uh, and, uh, um, and it was eventually solved, uh, in 1976, uh, by Kenneth Appell and, and involved Colin Harun, who actually died just last October. Uh, and, uh, uh, you can see that they've used graphs rather than maps to solve it. Well, they actually managed to solve it, uh, with the aid of a computer, uh, by reducing the whole problem to just 1,936 different cases, which he had to analyze one at a time. In fact, they later managed to cut it down to a mere 1,482. Uh, but, uh, it still made, it was the first major problem in mathematics, which was, which needed the aid of a computer to solve it. And, uh, um, so although the proof was acclaimed is a Japanese newspaper, uh, oh, and incidentally, um, uh, the University of Illinois, where they came from, they used this for their, for their postal, um, um, letters. Uh, so anyway, the, the, it was very, very popular. Uh, it was acclaimed, but it also can cause much controversy, uh, by mathematicians who consider problems to be invalid if they can't be checked by hand. Um, uh, it was, uh, after it came, I mean, I wrote this book, four Colors suffice, uh, on the history and, and solution to problem, highly recommended. Um, uh, and in fact, when Appell and Harken came to England to get to give lectures on their proof, uh, I, I was able to celebrate with them. But I'd like to con conclude with, with, with another related coloring problem, because coloring maps on the plane is the same thing as, is same, the same coloring on the globe. And you can think, here's a map on the plane. If you project it up, you get a map on the globe and the other way around. So I mean, here, here's a map, um, and you can color the sea and then, and then you, you get, get a map on the globe. So if you can, so, so four colors, four is the number of colors you need to color maps on a, on a, on a globe. So you can think of other surfaces from the simplest surfaces after, after a sphere is a Taurus or bagel, if you like. Okay? Or, and then you can have more holes in it, uh, like a pretzel or whatever. Why you want to color maps on pretzels, I'm not sure. But, um, so now one person who was involved with the history of the problem, the problem was proved by someone called Kemp in 1879, but the proof turned out to be Fallacious Kemp, uh, Hayward, uh, managed to find the error, uh, and proved the five color theorem that every map can be colored with five colors, but he couldn't do four. But he also generalized the problem, how many colors do you need to color a map on, on, on, on, on a Taurus? And he gave the correct answer of seven. Here is a picture of a map with, with, with seven, uh, uh, countries on here is a colored version. So seven's the magic number for a Taurus, uh, for, um, a double Taurus, one with two holes. The answer's actually eight. Uh, so how many do you need in general? And Haywood showed that if there are G holes in it, if g is the number of holes, then to get the number of every map can be colored with this number of colors looks a bit frightening. You take number of holes, multiply it by 48, add one, take the square root, um, add seven, divide by two, and then take the two apart. A actually that that formula just comes out naturally from the mathematics. So, um, but are, but, so he actually managed to show that every map can be colored with that number, but he didn't actually show apart from the Taurus. There are maps who actually need that number of colors and to prove that was called the Haywood conjecture. And so I'd like to end up by telling you slightly, this is the last slide, but can you prove that? Um, well, it was done by two gentlemen called Ringle and Youngs. It, it took a further, um, 78 years, uh, to prove the Hayward conjecture. Um, and it was done by Ringle, who was German and Youngs who was American in California. And they completed the proof, uh, that on the surface of G holes there are actually mapped, there are maps that need this number of colors. Uh, I'm not gonna go through the proof, there are whole books on the subject. Uh, but there're proof split into 12 separate cases, and nine of them had been done by, um, the middle of 67. Uh, and so Ringle, who I say was German, went to California, uh, on sabbatical for a year. The objects of the Sabba sabbatical was to do the remaining three cases, uh, and they succeeded after about six months, they succeeded. So Ringle and, and Jans had proved the Hayward conjecture. And, and to end with, I'd like to tell you a little story. There was great rejoicing in the grass theory work, uh, world that the Hayward conjecture had finally been solved. Uh, and a couple of months later, Mrs. Ringle was driving up the California expressway and she was going a bit too fast and she was stopped by a traffic cop who said, Hey, you're going too fast. I want to see your, your driving license. So Mrs. Ringle in Fear and Frelin produced her driving license and traffic cop said, Hmm, this is Ringle Ringle, eh, is your husband the one that sold the Hayward conjecture <laugh>? They're very, very well informed, the traffic cops in in California. Um, and, and Mrs. Ringle, um, said, yes, and there is, and uh, it turned out that the traffic cop's son was in Professor Young's calculus class, and the result was that Mrs. Ringle got let off with a warning. So if you're looking for applications of graph theory, that's the best one I know. Thank you very much. Knight's Tour problem that you guess semi magic square, when you add up all the things and all the entries in the grid, do you get that for all solutions to Knight's Tour? And does it work for boards of higher dimension sizes? It's an interesting question. Actually, I haven't heard it before. Um, the, the semi magic square we had, uh, was for eight by eight by eight ones. Uh, it'd be interesting to know whether, I don't know the answer, uh, whether it's been looked at very much for, uh, for other sizes. Oh, by the way, four, four by four can't be done. Six. Um, eight by eight can be done 10, 10 by 10 can be done. I don't know about the Magic Square or six by six. Uh, it's not clear. It's not obvious whether that can be done or not. Well, I mean, it's, it's, it is known whether, and I'm not gonna tell you, so I will leave it to you to decide whether you can find a Knight's tour on a six by six test port, but, uh, but I I don't know about magic squares on, on, on, on other sites, Right at the end, you talked, um, about the difference between necessary and sufficient conditions in the, um, Ringle Young's theorem, right at the start of the talk when talking about, um, uh, tor, uh, tours and er and Bridges of Kosberg, when then you produce various other examples and said, these can be done, these can't be done. Don't you actually ever said the why if everything is, um, uh, even number of vertices, it is actually a sufficient condition as well as a necessary one. Yes, I skated over that. Uh, so and so, so did Oyler. Oyer said, you know, if if you, if you're gonna, if you're gonna trace it, then the number of vertices of all degrees is zero or two. Uh, and, and, and he said, and it is quite clear that by adding enough bridges or something, it is quite clear that if that condition is satisfied, then the problem can always be solved. Uh, and so oiler was not very rigorous. And in fact, the proof of the other way around, um, oiler was 1735. Uh, and it wrote up in 1736 proof, uh, that that, that it, it's necessary and sufficient wasn't until 1871. Uh, it was, um, um, what's that called?, I think, uh, was walking off a corridor, uh, in Vienna, the University of Vienna. And he'd been working on such problems, uh, and, and, and, and he, he happened to mention what he'd done, uh, and, and how he'd done it to a colleague of his, and then he died. But fortunately, his colleague had listened to what, what this person said, which doesn't usually happen. Uh, and, uh, and he, uh, um, and he remembered enough to write up the paper. So it is necessary and insufficient. I did skate over it, so did oiler. I'm in good company. Uh, but, but, but the actual proof of the other way around was not done until over 130 years later. And could I just ask one final question? What's your next book going to be about? Do you have a next book schedule? Because we we look forward to them. Uh, well, I, I, I'm on number 56 now. 57. Um, well the, one of the next books is the one that I, I, I showed, uh, um, there we are. Um, I'm, we just handed this one, and so this might be the next one. Uh, I'm working on four at the moment. Um, I, I'm two, I'm writing and two I'm editing And the, and the others not about graph theory or always, Um, I, I think I gave a talk here. Well, I, no, I wrote a book on Oxford. I edited a book on Oxford civilian Professors of Geometry, which are the second oldest, uh, geometry professors in the country. Um, Gresham College of the oldest of course. Um, and, uh, and so I edited a book which came out last year on the, on the, on the civilian professors of geometry. But I felt there's also a need for the civilian professors of astronomy. Uh, unfortunately, I dunno any astronomy. Uh, but I'm, so I'm co-editing it with, uh, a colleague who happens to be the current civilian professor of astronomy. Uh, and so I think we're gonna make quite a good team. We've just started on that. Good Heaven. Well, that's something to look forward to. Um, I just wanted to say thank you very much on behalf of the audience on online and in the room. And, um, just to flag up, we do have one more, uh, well, we have two more lectures left in the program. Um, tomorrow we've got, so Christopher Ren architect and, and courtier by our former Provost Simon Thurley, which is gonna be amazing. And, uh, you can probably watch it online if you can't get tickets in person. And finally, the grays in reading, which is on, uh, where we're at with freedom of expression, which promises to be very interesting too. So, uh, a very warm thank you to to Professor Wilson.