Connecting the Dots: Milestones in Graph Theory

foreign but these graphs are not the curves like Y equals X cubed that you see in maths books but are diagrams that depict connections between things such as the London Underground network of stations linked by rails or chemical molecules as shown here with carbons 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 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-1936 not a very exciting title in which we 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 this arose out of the doctoral thesis of an open University student of mine and describes in particular the American aspects 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 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 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 theoretical results of a surprising variety and depth and indeed graph Theory today 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 out and 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 some of these will be familiar to you there's the koenigsberg bridges problem the night's tour problem in chess the utilities or gas water and electricity problem a problem arising from Goodwill Hunting the minimum connector problem and map color problems but first let me introduce some technology which are some terminology which I'll need most of which is is pretty straightforward so in this talk a graph consists of some points usually called vertices or nodes which are join in pairs by lines called edges or arcs so on the left is a graph with five vertices are 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 K5 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 two vertices of degree three this one and that one and a vertex of degree four and of all the degrees are the same the graph is called regular so the complete graph K5 is a regular graph of degree four there are four edges out of each vertex 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 a couple of quadratic quadrilaterals there's one there's another one and at the outside pentagon but the graph with no Cycles is called a tree like a family tree so on the right at the graph on the right is a tree which is well known for its bark I've been telling that joke for 50 years 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 some some hexagons like this one here 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 because all Cycles there well it has no Cycles at all let alone older 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 colliningrad as you can see there are four parts of the city one two three four joined by all connected by Seven Bridges and the problem that this is 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 there and then there oops I've left that that one so let's start with that one that one yeah oh I've left out that one so it's not awfully easy to do that and in fact the citizens soon found themselves unable to do so but is this really the case or or is there such a route and at this stage we welcome Leonard Euler the most prolific mathematician of all time um who has actually lectured here at Gresham College 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 leibnized first mentioned calling it The geometry of position this is concerned only with the determination of position its properties it does not involve measurements nor calculations made with them it hasn't yet been satisfactory to determine 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 so it's a geometrical problem but one which doesn't involve any ideas of measurement or length or angle or anything like that and the problem he's referring to of course is the konisberg problem so how did Euler 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 distance have now gone the important thing is the connection between the four land areas and the connections formed by the Seven Bridges and he then used a counting argument for Essex for a successful walk whenever you enter a region you must be able to leave it which means 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 five three three and three five round region a three for B three for C and three for D and these numbers are all odd so the walk 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 an end in the other an Euler Illustrated this in this example below this also appears in his paper of 1736 he Illustrated 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 three for d 5 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 incentive 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're starting one odd degree and end in the other so for the koenigsberg problem we get this graph here and the degrees are again five five five three three three which are all odd there are four of them so there's no solution now regressively it's often claimed that this was how Euler originally solved the problem even just a couple of couple of months ago I saw an article which said that Euler solved the koenigsberg problem by trying the graph he did not draw that graph and as far as I can find out the earliest appearance of this koenigsberg graph seems to have been in a popular book of mathematical Recreations written as late as 1892 more than 150 years after Euler originally solved the problem and indeed when the quadrennial international Congress of mathematicians was held in 2014 in Korea the Congress issued this postage stamp of the of the kernings of konisberg the koenigsberg map with with the graph and it says at the top Leonard Euler 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 between became quite popular in the 19th century and here are three examples we can certainly trace the first one in one continuous pinstroke because the vertex degrees are all even they're all six one way is go around the outside then jump when it's time zero two four six one three five zero and then jump two at a time and so on and 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 walk will take out two of them so it means you're going to need at least four walks and then you find you can do it with four you start to go all the way around and then you add these three separate ones so four is the answer of that question how about the lower one this is a nice picture it was introduced in 1847 by Johann Benny Benedict listing he was a mathematician particularly interested in in the mathematics of Optics and he was the person who introduced the word topology to mathematics topology is often described as rubber sheep geometry if you if you if you draw a picture on a bit of Robert and you stretch it of course you lose all 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 word first of all in a letter he wrote in 1838 and then in in an article he wrote in 1847 where he presented uh the last two of these dark green diagram tracing puzzles and 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 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 chess enthusiasts as the night tour book night's tour problem in this problem many centuries old asked whether a knight can visit all the 64 squares of a chessboard by night's moves and return to its starting point and knights moves you can recall that a knight always moves two squares in One Direction and one square in a perpendicular Direction so it can go through any of the squares marked here two in one direction and one in the perpendicular Direction well before embarking on that problem in generality let's see what it entails and what it's linked with graph Theory and so I'm going to look at the simpler example of a 4x4 chessboard the one down here first of all you can draw a graph with 16 vertices with the vertices corresponding to squares of the chessboard and the edges correspond to night'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 start but this is impossible because if you to to pick up this vertex you're 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 suddenly for a five by five one to pick up all the these four corners here and you're going to 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 seeing 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 the number of black squares must be the same as the number of white squares because there's a number of black squares and white squares are the same that's impossible when they're 25 squares altogether and so similarly there are no Knights chores on a seven by seven seven chessboard or a nine by nine one or for any chess board with an odd number of squares so attorney now back to the original H by h chessboard we meet Euler again Euler seems to have been the first mathematician to study the problem mathematically the two papers that came out in around that time he Oiler wrote One in 1759 and there's another paper by someone called vandermond who's known in mathematics for something called the vandermond determinant wrote six papers none of which mentions anything about the so-called vendor one determinant but there we are but Euler got interested and and he he started the problem and first of all he came up with this solution one two three four the trouble is that 164 don't match up but he did actually work a bit harder and he did find some solutions uh to this problem and here's a solution this is a particularly interesting one here you can see the night starts here and goes around here and if you count the squares as you go one to two to three to four to five and so on um then you get this pattern of numbers here and what's interesting about this particular petal of numbers is not only does it give you a nice tour but it's actually what we call a 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. and 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 it was only very recently I think that there's a computer search which shows that there is no unfortunately there is no solution where you can get the diagonals working as well but even so that's that's pretty remarkable I think and on the top right you can see Euler's solution for a 10 by 10 chessboard with the numbers from 1 to 1 to 100 all linked up by night's moves again one two three four and so on well these problems are visiting all the vertices 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 but anyway 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 and so where does the fly go the fly starts here and goes around there I'm sorry I once gave this lecture using an overhead projector actually and uh unknown to I couldn't see it but the audience called it and if there was a fly there and just when that started it started walking along the path and so the audience were in fits of laughter and I didn't know why but they were so that is how you do it for a cube uh so the solid lines gives us a route that fly can take 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 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 an octave octahedron eight faces and if you squash it flat you get this picture here and it's quite easy to see the to find the PATH which goes through all the vertices and we can ask the same question also for a dodecahedron uh the dodecahedron's got 12 pentagonal faces and and if you squash it flat you get this picture and the red the red path tells you a part gives you a path through all the vertices and that's a particularly interesting one historically because in the 1850s in connection with some researchers in algebra the Irish mathematician so William Rowan Hamilton asked for such such roots on a dodecahedron subject to certain conditions for example can you find and you can easily trace this BC you just followed a consonants bcdfg and so on but supposing you say you're told that you have to start j-e-l-d-b okay how many ways can you complete it there are a number of questions that he posed there which he found quite fun um and in fact so much fun he found it was he turned the problem into a game called the icosian game um where the 20 vertices correspond to the 20 consonants of the alphabet and we seek a voyage around around the world so if you start B and C and so on B was Brussels C was Canton and the idea was to it is to get to zed which is Zanzibar and he sold this game to a games manufacturer for 25 pounds which was a wise move as it didn't sell I once went to the Irish Academy where they actually have have an original they're all solid ones but the best ones are the flat ones here and I went in and and there are lots of people there studying sixth Century Irish manuscripts some of them not just so they've been there since the 6th century and now as there I was with all my pegs pop and putting things in in having great fun getting some very funny looks now because of Hamilton's Fame and influence Grassroots have a route through all the vertices are now called hamiltonian but they should really be named after the Reverend Thomas Pennington Kirkman a Lancashire 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 children for Kirkland's writing about Cycles on polyhedra in general before Hamilton did as I said 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 after 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 starts off um if we cut into the cell of a bee then you get this particular pattern here which I'm prepared to believe and to see why it has no hamiltonian cycle we noticed that the graph is bipartite all of the Cycles have even length which means that we can color its vertices 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 because 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 chessboard so talking about hamiltonian grass before moving on let me conclude a slightly more recent result because in 1880 the question had been raised as to whether every cubic polyhedron that's one with three faces meeting at each vertex Each corner whether every cubic polyhedron has a hamiltonian cycle as as Dr Cuban has does the dodecahedron well Kirkman thought about this in 1884 and couldn't decide whether it does or not and say it mocks a life alike a 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 in this country's history in Bletchley Park he was the mainly the person who who decoded the Hitler's tonic codes at Bletchley Park and but he later became a major figure in graph Theory and in 1946 Todd wrote a paper which actually follows from some of the graph theories he was doing at Bletchley Park uh he he published an example of of this polyhedron here if you think of wrapping it round you could actually get a polyhedron there that's a flattened version and and that's got 46 verse vertices and it has no hamiltonian cycle so after all that time he found a counter example he answered the question with the answer no and since then a few other examples have been some small examples have it have been discovered so moving on to our third third problem um it arises from a utilities problem in which three unfriendly neighbors a b and c who may usually call Mr angry Mr beastly and Mr Cross they wit 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 this cross now the origins of the problem aren't known although certainly presented by the American Puzzler Sam Lloyd who wrote puzzle books in America around 1900. and on the right is an attempted solution where I've tried to insert the the nine the nine links so 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 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 you draw uh the three uh three utilities to three houses can you link them up with nine edges so in graph theory in craft 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 okay and so what we're asking a graph is play now if you can draw it on the plane without any Crossings so the question is is this planar so nothing could be much plainers than that so we can ask uh we can ask this question and and the answer is no to see why you notice that six of the six of them form a hexagons 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 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 if you put this one outside then these two will have to be inside but they'll still cross so in either way there's no way of doing it the graph cannot be drawn in the graph 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 but the important person that I want to mention is a famous polish topologist called kurachovsky whom I met once actually was very interesting um so some graphs such as the uh such as this these are planar because 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 this one is not playing and that's quite an easy easy article thing to do as well so these two are not planar the important result of curatorski is these are essentially the only ones because if you have a graph which is not planar then it must contain at least one of these two and that's quite a remarkable result interestingly curatoski himself said that 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 and so he had to deal with that as well but that's a very famous result in graph theory that it which describes completely when a graph is planar or not these are the only obstacles but we can say more about planar graphs and this is Euler again in 1750 Euler observed that for any polyhedron the number of faces plus a 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 twelve plus two dodecahedron uh there are 12 faces there are 20 vertices as we as we saw 30 edges 12 plus 20 is 30 plus 2. and here's a great run by causative cosidodicahedron and so it's called in the trade and you can see immediately that it has 62 faces 120 vertices and 180 edges and 62 plus 120 is 180 Plus 2. so it doesn't have to be regular you can have to have different types of faces and and and the the result still works um so this is an important result how did it arise well let me show you the place it first appeared Euler had been in some Petersburg for a time he then moved to Berlin in 1741 and in 1750 he wrote to his friend and colleague Christian goldbach um who is still in in Saint Petersburg and who is famous for an unproved conjecture on prime numbers some of you all know of gold bars conjecture and the formula uh eider's formula for is right here h plus s equals a plus two here H is he dry now uh Latin um he drives for Latin for faces s it talks about solid angles the solid angle is if you like a vertex and and a is accies which is an edge interestingly Euler was I mean lots of people have looked at polyhedra in the past the Greek the ancient Greeks had Johannes Kepler had a lot in in around in the 1600s but no one had ever looked at edges before or tried to count them and it was and so it's all introduced the word accies for ages and so that's that age so this is the first appearance of all this formula and further down the page of the letter he takes a particular example and he and he checks that it works for that so I thought you might like to see that and the former also works for grass joining 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 them out these are these are their graphs and you can check Euler's formula for each of them that works and we can actually use Euler's formula to prove results about polyhedra now this polyhedron here is called a truncated truncated icosahedron or some people call it a football and as you can see it's made up from pentagons and hexagons with just three faces meeting at each point [Applause] a more complicated examples of polyhedra made of pentagons and hexagons are the chemical molecules known as followings or Buckyballs and here's his one is C60 which is essentially the same as this but they're lots more complicated ones all made with pentagons and hexagons as I say they're called fullerings and Buckyballs and their name comes from Buckminster Fuller the American architect who used the idea when constructing his geodesic domes that you can see below for various exhibitions and World fairs 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 a difference between them so here is uh here is a calculation right what's interesting is that for any of these polyhedra where you've got Pentacles and hexagons with three meetings at a point there can be lots and lots of different numbers of hexagons but there are always exactly 12 pentagons and we can prove that using Euler's Euler's formula so first of all so I'm going to assume I got a soccer ball with pentagons and eight hexagons so the total number of faces is obviously P plus h now I'm going to count the edges around the faces so there are pentagons and five edges around here it gives you five pages around around the pentagons there are eight hexagons and six edges we're also going to get six H edges around there so the total number of edges is is is five P plus plus plus 6h it seems oh but each Edge has got two faces so each if you do this you're going to count each Edge twice once for this face and once for this three so in fact you get chewy and not and not are not e and suddenly you can count the three edges at each vertex and you get the similar thing 3v well 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 get five P plus two six H again so so you've got f e and V and you can now substitute them into Euler's formula so here's f V is a third of this is e which is a half of this plus two so there's that formula there well fortunately h plus two H and three h they cancel and that leaves a an equation which you can solve to get P equals 12 so there must be exactly 12 pentagons so we've proved the result and you can also use Euler'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 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 that the janitor played by Matt Damon it's walking down the corridor in the Massachusetts Institute of techno Massachusetts Institute of Technology MIT uh he and 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 an exceedingly difficult problem in functional analysis well don't worry about what folks analysis but it's actually a very very simple problem in graph Theory to draw all the homomorphically 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 and they all 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 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 and and then down below here are some chemical trees now these chemical trees have got four carbons which form a carbon tree with with eight with 10 hydrogens around them these are called alkanes or paraffins so lots of paraphernalia here uh and uh um so here are two different molecules with the formula c4h10 and there is no two different ones is because there are two trees with four vertices look at the carbons you get with this one and you get this one and 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 isomers are there with with say 10 color lessons here are all the trees with six vertices there are six of them so how many trees have ten vertices how many trees have a hundred vertices these are mathematical problems which when they want to try and solve and the particular one we're talking about a tree is homeomorphically irreducible if it has no vertex of degree two well these vertices of degree so that one's no good this one's no good this has got a Vertex a degree two that one's no good that one's no good but these are okay so there are two homomorphically irreducible trees and six vertices and there are so many a number with ten vertices and I'll leave that as an exercise for the reader so you can you can solve the matte Daemon MIT problem yourself I'm sure without much difficulty oh I should incidentally say that some problem these counting problems were studied very much in the second half of the 19th century in particular by two English mathematicians Arthur Kaley and James Joseph Sylvester they did a lot of work very important pure mathematicians in this country so vestra also went in fact to America and there's a whole chapter about him in this wonderful book here but there's another result of Kaylee which is quite interesting which involved counting label trees now although there's just two trees with four vertices if you start labeling them I mean here's here's a 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 in different ways then you can actually see that there are 16 different different possibilities 16 ways of of labeling labeling this tree I mean I've drawn them in different ways but you can see that this is this is true one three four this is one two four three three one two four one three two they're all different ways of labeling it and so how many ways can you label a a tree with with four vertices the answer 16 the five vertices is 125 six verses it's 1296. uh Kaylee came up with the formula that if if a inverse of C is the number of label trees is n to the N minus two so this is 4 squared 5 cubed six to the fourth and so on unfortunately Kaylee proved 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 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 routes 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've just seen that 125 possible trees um we don't want to go through them all let's look at a few I mean I could have taken this tree here all that has cost 23. here's 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 for finding the shortest tree we don't want to have to go through 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 H4 because that will create this cycle so I ignore that one and that's just the next one that's this five okay so I've got this one this one and this one I can't now choose this one which is six because that gives me a cycle and I can't choose this one which is six because that that because that that also that gives me this cycle so I've got to choose the seven so I've got this oh and I've I've finished so so I've stopped and that has total cost 17 which is better than 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 is unique there's just one one solution and this method for finding minimum cost trees was introduced by Czech mathematicians in the 1920s subject was revised was revived in America in the 1950s a couple of important papers by Chris Carlin sometimes called kruskar's algorithm and someone called Prim and in prim's paper here is his solution for the 48th cotermine stent states that in other words not not Alaska and Hawaii but the other 48 states this is the minimum the minimum tree uh going through all of those those capitals now interestingly uh that that's a problem which has a complete solution 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 where you've got a traveling salesman who visits a number of cities selling graph Theory books or something and they want to visit the citizen return to the 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 for this the same exact we could take we could go around the outside that gives you 29 you can take this star path of the next train 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 a it's the optimum solution with total cost 26. but I had to do it by trial and error there is unlike the ingredient 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 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 were resolved and this apparently is the minimum cost for the capitals of the 48 states so we come through our lost problem now in fact two problems on the covering of maps in 1852 it was found that four colors are 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 a fall coloring of the 48 American states 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 count four neighboring regions so each of them must be different from the other three so you'll get a need to 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 alternating colors you're going to need three for the outside ring an organ had to be different from the middle one so there's another one where you're going to need four and this example here occurs with Nevada you've got the five states around from a ring with Nevada in the middle so um so and the connection with graphs by the way I mean here's a map of the states of Australia instead of coloring 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're really coloring if you like the vertices of a graph 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 when certain problems are solved this is the language that graph theorists usually use uh well the history of the Four Color problem that I've lectured on here before you can probably find it on the website uh so I'm not going to go through all that I'm going to cut through to the end uh of of it where it was finally solved uh you can act can you prove that all maps can be colored before with just four colors this took 124 years to prove and and the argument is is quite complicated uh it's not deep but it's difficult uh and uh um and it was eventually solved in 1976 by Kenneth Appel and and Wolfgang hulkan who actually died just last October and uh you can see that they've used graphs rather than maps to solve it well they actually managed to solve it with the aid of a computer by reducing the whole problem to just 1936 different cases which she had to analyze one at a time in fact they later managed to cut it down to a mere 1482 but 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 the University of Illinois where they came from they use this for their for their postal um letters so anyway it was very very popular uh it was acclaimed but it also can cause much controversy by a mathematicians who considered problems to be invalid if they can't be checked by hand um it was after it came I mean I wrote this book four colors suffice on the history and and solution of the problem highly recommended and in fact when Appel and harcom came to England to get to give lectures on their proof I I was able to celebrate with them but I'd like to conclude with with another related coloring problem because carrying maps on the plane is the same thing as essentially the same as coloring on a globe and you can think here's a map on the plane if you've projected up you get a map on the globe and the other way around so I mean here here's a map 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 the on a globe so you can see your other surfaces from the simplest Services after after a sphere is a Taurus or Bagel if you like okay or and then you can have more holes in it 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 Ken Haywood managed to find the error and prove 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 a Taurus and he gave the correct chance of seven here is a picture of a map with with seven countries on here and here is a colored version so seven is the magic number for Taurus uh for a double Taurus one with two holes the answer is actually eight so how many do you need in general and Hayward show 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 frightly you take the number of holes multiplied by 48 add one take the square root add seven divide by two and then take the integer part actually that that formula just comes out naturally from the mathematics so um but on 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 which actually need that number of colors and to prove that was called the Hayward conjecture 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 took further um 78 years to prove the Hayward conjecture and it was done by Ringle who was German and Youngs was American in California they completed the proof that on the surface with G holds they're actually met there are maps that need this number of colors I'm not going to go through the proof there are whole books on the subject but they're proof split into 12 separate cases and nine of them have been done by um the middle of 67 and so Ringle as I say was German went to California uh on sabbatical for a year the objects of the sabbatical was to do the remaining three cases and they succeeded after about six months they succeeded so Ringle and Youngs had proved the Hayward conjecture and to end with I'd like to tell you a little story there was great rejoicing in the grass Theory Work World the Hayward conjecture had finally been solved 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 friendly and produced her driving license traffic cop said this is Ringle Brinkley is your husband the one that sold the Hayward conjecture they're very very well informed the traffic cops in California um and and Mrs Ringle um said yes and there is and uh it turned out that the traffic cops sons 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 Mike's tour problem that you guys send me magic square one you add up all the things in other entries in the grid do you get that for all solutions tonight'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 we're the the semi-magic square we had uh was for eight by it was eight by eight ones uh it'd be interesting to know whether I don't know the answer 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 ten ten by ten can be done I don't know about the magic square or if six by six and 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 well and I'm not going to tell you so I will leave it to you to decide whether you can find the knights Tour on a 6x6 chessboard but I I don't know about magic squares on on other sides right at the end you talked about the difference between necessary and sufficient conditions in the Ringo Young's theorem we're at the start of the talk when talking about um other examples and said these can be done these can't be done don't you actually ever said why if everything is um even number of vertices it is actually uh sufficient condition as well as a necessary one yes I skated over that uh so and so so did Eiler and Euler said you know if you're if you're gonna if you're going to trace it then the number of vertices of all degree is zero or two uh and and he said and this is quite clear that by adding enough fridges or something it is quite clear that if that condition is satisfied then the problem can always be solved uh and so Euler was not very rigorous and in fact the proof of the other way around um oil was 1735 and it wrote it up in 1736 the proof uh that it's necessary and sufficient wasn't until 1871. uh it's um umter I think I was walking off a corridor uh in Vienna the University of Vienna and and he'd been working on such problems uh and and he he hadn't to mention what he'd done 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 and he uh um and he remembered enough to write out the paper so it is necessary and sufficient I did skate over it so did Oiler I'm in good company uh 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 look forward to them uh well I I'm on number 56 now 57 um well one of the next books is the one that I I showed uh um there we are and we just handed this one and so this might be the next one I'm working on four at the moment um I and two I'm writing and two I'm editing and the and the other is not about graph Theory or always um I think I gave a talk here well no I wrote a book on Oxford I edited a book on Oxford civilian professors of geometry which are the second oldest geometry professors in the country Gresham College of the oldest of course um and uh and so I edited a book which came out last year on this on this on the civilian professors of geometry but I felt there's also a need for civilian professors of astronomy uh unfortunately I don't know any astronomy but I'm so I'm co-editing it with a colleague who happens to be the current civilian professor of astronomy and so I think we're going to make quite a good team we've just started on that good happens 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 where we have two more lectures left in the program um tomorrow we've got Sir Christopher Wren architecture and quarter by our former Provost Simon Fairley which is going to 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 where we're at with freedom of expression which promises to be very interesting too so a very warm thank you to to Professor Wilson [Applause]

Channel: Gresham College

Views: 6,256

Keywords: Gresham, Gresham College, Education, Lecture, Public, London, Debate, Academia, Knowledge, maths, geometry, mathematics, graph theory, calculation, motion, measurement, Konigsberg, Knights-tour problem, good will hunting, vertex, cubic, Euler, Leibniz, magnitudes, Icosian, Tutte, Kuratowski, Planar, polyhedra, Cayley, Appel, Haken, Heawood

Id: W3NoY3SQgrU

Length: 60min 53sec (3653 seconds)

Published: Mon Jun 26 2023