Today is gonna be about planar graphs. Graphs that can be embedded in the plane. (Brady: Okay. So what's a graph and what's a plane and what's embedding?)
- I'll tell you all about that So a graph consists of a bunch of points, that we call vertices, and then some pairs of vertices are joined by a line that we call an edge and - like this. And some pairs of vertices don't have anything between them. So for example, this is a graph, this is also a graph called the house.
- (Brady: You actually call that a house?)
- We actually call that a house, yes We also - it's official name is P5 complement. It's nickname is house (Brady: Professor when I was at school a graph to me had like an x and a y-axis and a line and things like that,) (but this is not what that looked like)
- Completely unrelated, it's just an unfortunate overloading of a word. Completely different concept at all.
- (Brady: Okay, cool. So this is what our graph - this is a real graph?) Yes, exactly. There we go. Thank you, somebody for - somebody who understands. (Brady: Okay) And then the question is which graphs can you draw - so this is a plane - piece of paper is a plane, and the question is which graphs can you draw in the plane so that edges don't intersect. So what does the mean edges don't intersect? Don't uh, intersect where they shouldn't. Like for example in this graph this edge and this edge intersect over here but we meant it. They will intersect over here because they have a common vertex over here. But for example if I make this drawing. So right so the vertices are 1, 2, 3, 4 the edges are 1, 2, 3. This edge and that edge they intersect and it's not a fair intersection. They just intersect because I drew it like this. I could have drawn it like that. So a graph is planar if you can draw it in the plane or in a piece of paper in such a way that two edges only intersect where you intended them to intersect, only intersect at a vertex. (Brady: Professor, if you draw a graph and edges intersect) (does that mean it's not a graph, or it's invalid or it's like breaking the rules? Or is it just a different kind of graph?) It's a different kind of graph. It's a - so a graph, this is a graph and this is a graph it's called an abstract graph. And then you can ask about or talk about planar embedding of a graph. And what that means is that you've drawn it like this. This is a graph but not a planar embedding. This is only illegal if what you're after is planar embedding.
- (Brady: Is a planar embedding) (somehow better?)
- It's probably, possibly good for some applications, like if you want to, I don't know build a side component or something, which I don't know anything about. But it's just it's just another property right and maths, what do we do? We think of an object, we think of a property and then we say, do all the subject have this property? Do some of the subjects has this property? Can you tell if you have this property what other property do you have? Can you characterise when you have this property? So being planar is a property some graphs have and some graphs don't have. And I actually haven't told you what planar means yet I think. I told you what the planar embedding is, but I haven't told you what what a planar graph is. (Brady: Okay)
- So graph is planar if it has a planar embedding. For example, this graph has a planar embedding, namely that one. This graph also has a planar embedding, namely this one. This graph no matter how hard you try it does not have a planar embedding.
- (Brady: You couldn't cheat?) (or manipulate and move the - )
- That is exactly right. That is exactly what it means. Here's an example that looks almost almost as complicated as that, right? This is only different from that by one vertex? But this you could actually embed in the plane because what you do is you - let me number the vertices so you believe me it's an embedding. And then you do this. Right. So let me explain why this is the same with that. What do we care about? We care about vertices and we care about which pairs of vertices are adjacent. So vertices are 1, 2, 3, 4; 1, 2, 3, 4, that's fair. Now here every pair is adjacent. So let's check that also here every pair is adjacent. 1's adjacent to 2, 2 to 3, 3 to 1, 4's adjacent to them all. So this abstract graph is the same as that abstract graph. This is a planar embedding, this is not a planar embedding.
- (Brady: Do edges have to be straight?) (Like could you have kept these vertices in the same places and like drawn curved lines around the place to - as well, or?) I just don't have to be straight here, there's a theorem that says that anything you can embed with curved edges you can embed with straight edges, it doesn't matter. So you're asking, me could I leave these four vertices is in place and just make the edges? Yes. So what I would do is - so I could make this completely asymmetric, ugly drawing; or this beautiful drawing.
- (Brady: Yes, less elegant)
- But on that hand, you know, they see - you can see how to get it? Which I think has a lot of value.
- (Brady: So it's not a conjecture) (it's a theorem that any planar graph that you can draw with curved edges you could also have done with straight edges?)
- That's right (Brady: Oh, that's really cool)
- Yeah it is amazing.
- (Brady: Yeah) I learned this theorem in the right time in my life, I wasn't in high school when I heard about it. So I am in fact as amazed by this theorem as everyone should be. I haven't, you know become jaded by the time I heard of it. (Brady: But you can't do any trickery with that like you did there. That one's - )
- No trickery There is one more where we can't do any trickery. And in fact, that's usually how introduction to planar graphs is taught. So you have three houses and three utilities. (Brady: Those houses are actual houses. They're not these houses?)
- I don't know, you tell me No way to tell. You want to put lines between the utilities and the houses, right? You want to put power lines and phone lines and water pipes and it's important that they don't intersect each other so that you can fix, fix them independently or some other story along this lines. And so the question is can you? And so, you know, you can try you can, you can - let me connect this one like that So you got the electricity and you can connect the phone and we can go here. Maybe you can go there and maybe you can go there. And you can start with the water but you're not gonna be able to finish. And err and it's a theorem that, you know, that you're not going to be able to finish. So if I draw this as a graph, everybody on the first side is adjacent to everybody on the second side. And this is called K3,3 By the way, this guy's called K5. So K5 and K3,3 are two graphs that do not have planar embeddings. They're the two smallest graphs that don't have planar bearings. Okay. K somewhat mystifyingly stands for complete, and so this is the complete graph on 5 vertices. Now this is not the complete graph, because obviously there are some pairs that are non-adjacent. You have two sides, this side and that side and everybody on this side is adjacent to everybody on that side. That's called the complete bipartite graph. And the way we know that it's complete bipartite and not complete is because we have two numbers instead of one number. So Ka,b is a here b there, all adjacent to each other. Kt is t, all pairwise adjacent. (Brady: Is there a way to tell what's embeddable and what's not?) So there is a way to tell. And actually it's a lovely theorem, it's a theorem I can tell you. You believed me that we can't embed those. In fact, maybe you shouldn't believe me but there is an elegant proof of it. That you - you need to know a little bit of geometry, you need to know something called Euler's formula and from that it's actually very easy to see that these two graphs are not embeddable. But let's say we believe that they're not embeddable. So then here's another graph that's not embeddable. If I take an edge here and I, what we call, subdivide it. Which means I'll draw some vertices in the middle. That's another graph that's not embeddable, right? Because if I could embed this, now just delete vertices and so and you can do that for any edge you like here, you can do there. So these are all not embeddable, and they're called subdivisions. So we know that K5 is not embeddable, K3,3 is not embeddable. And we also convinced ourselves that subdivisions of them - they're all not embeddable. And the theorem is, that's it. The only reason some graph is not embeddable is because there's one of those bad guys sitting in it. You can delete vertices and edges from it and find either a subdivision of K3,3 or a subdivision of K5. It's called Kuratowski's theorem. (Brady: Just those two?)
- Just those two. It's a miracle! (Brady: So though - they're like the two spanners in the works?) Exactly. So the theorem is: G is planar if - if and only if, G has no K5 subdivision and no K3,3. (Brady: Wow!) (So every single graph - if I drew you the most complicated graph in the world, and it was non embeddable) (you'd be able to find that in there somewhere?)
- That is correct. That's the only reason something is not embeddable. So these graphs they're very special. What - most graphs are not like that. It's a very special kind of graphs that are embeddable. It's not that other graphs - that other graphs are bad, other graphs are good. In fact, most of the work is with other graphs. It's just if you work with those, you can suddenly prove much stronger theorems. It's like you know, you can think of all numbers or you can think of powers of 2.
- (Brady: Or prime - )
- Prime numbers Powers of 2 are much nicer than normal numbers. It's not that the other numbers are not good, it's just you know - in some way the other numbers are more interesting because they're not powers of two. But there are certain theorems you can only prove about powers of two. So probably the most famous theory about - theorem about planar graphs is that you can colour them with four colours. So maybe I'll talk about a little bit? So colouring graphs means you want to colour the vertices so that adjacent vertices get different colours. So, for example in this graph I can colour this blue, and this green, and also this green, this red, and just like this blue and, and this is a colouring. This is a colouring with three colours. So adjacent pairs get different colours; this is colouring with three colours. And you can see that you couldn't do it with fewer colours than three, because you have these three vertices all pairwise adjacent. So you have to use three. And now the question is if I give you a graph what the smallest number of colours you can use to colour it? So one thing you immediately notice is that if you have a bunch of vertices all pairwise adjacent then you need at least that many colours. In fact sometimes we need many more. This is a whole different branch of math that's very active at the moment, but often you may need many more but at least this is an obvious lower bound. Now, in planar graphs we know that you don't have a K5. So you're not gonna have five vertices all pairwise adjacent. So at least this naive bound only would give you, that you need four. And the theorem is four is enough. The theorem is, it's called the four colour theorem. Every planar graph is four-colourable. It comes from map colouring. It was actually conjectured by, by a cartographer in, in eighteen something 1863 I think. Where he said if I have a map and I want to colour the countries so that adjacent countries get different colours, how many colours do I need? I seem to be noticing that four is always enough. And uhh, and the answer is yes, four is always enough, because you can easily translate colouring a map into colouring a planar graph. What you do is take a map, alright, so the countries are this outside ring and then those triangles. So now I'm going to make a graph out of it. I'm going to put a vertex in the middle of each country. If two countries share the border I'm going to put an edge between the two vertices. Another way to think about it I'm kind of, turning the edges. This edge used to go like this between these two countries, but now I'm gonna put it perpendicularly. So because this is a mess let me just draw the blue graph again, so this is already better, but now I can draw it even better. You can do that. So anyway, so the black thing there was a map. The blue thing here is a planar graph. If I colour the vertices of this planar graph and then I use these colours to colour the regions of this map, the countries of this map, it's it's the same problem. And so now the theorem is that it's enough to use four colours. For all of this to be true you need some slightly technical assumptions. Like in this map, you can't have Alaska. The countries have to be contiguous or as in math we say connected. Because it's very easy to construct a map where each country is a hundred islands and you need a hundred colours to colour it, but that's not what we mean. What we mean is we only - all countries are connected.
- (Brady: With the planar embedding, like if there was a really complicated) (graph here on the board. Could you look at it and) (apply some algorithm or rule to be able to - )
- So you must be mind reading, I just wanted to talk about that. (Brady: Okay, do you need more paper?)
[both laugh] So I don't want to talk to you about an algorithm, but I'm going to talk to you about how to tell that something is not embeddable - or one way to tell that something is not embeddable, right? So I said K5 is not embeddable; and I say just, just name it because it's hard to prove. But actually is it just one fact I tell you, then it's going to be easy to prove. And the fact is, the theorem is in a planar graph: let G be a planar graph. And then we have V is the number of vertices, and E is the number of edges. Then E is at most 3 V minus 6. So now let's check that this guy fails. Because it has five vertices, right. And the number of edges - so all pairs of five vertices, that's 10 edges. And now you can see that 10 is not less or equal than 3 times 5 minus 6. So this is for sure not planar. So now armed with this wisdom you want to prove that this is not planar.
- (Brady: Our electricity, water, telephone one) So let's count. The number of verses is six. The number of edges is nine. And then if you do that, it does come out sadly. Nine is at most three times six minus six so that's not gonna work. This is not an if and only if. This is just a - a tool. But in fact you can look at the proof of this theorem more closely and you'll find out that if your graph doesn't have cycles, cycles of length three, then you can improve this.
- (Brady: So there's another test?)
- Yes. G is not planar and G has no triangle, then E is at most 2 V minus 4. (Brady: Alright) And then - so first of all, let's check that this is going to be helpful. So E is nine, 2 times 6 minus 4 is not at least 9. That's a good start. Now we just need to convince ourselves that we can use this theorem to test this graph. So what do I need to check? I need to check that this doesn't have triangles. But if you think about this for a minute, this graph has a property that vertices come in two flavours and all the edges - and all the edges you have go between them. Look at a cycle, start looking at this vertex. It's gonna go right, left, right, left, right, left and eventually it has to come back. So it's gonna have an even number of vertices. So in particular it doesn't have triangles. So now you might ask well, you know this worked very well to test; maybe it's true the other way. If I give you a graph and I promise - and I thought well it makes sense right if I give you a bunch of vertices and in order to embed it you need that there aren't too many edges, right. If there's too many edges it's too much of a mess, you can't embed it. And maybe it's true that if I give you a graph that has a bunch of vertices and there are not too many edges, then you can embed it. But...that doesn't work unfortunately. So false: E, small as a function of V, implies planar.
- (Brady: But you'd think it would be easier if there were fewer edges) (like - or is that not the case?)
- Well, so let me show you an example and you tell me if it's easier or harder. Start with the K5 which we know is a bad guy, and now draw lots and lots and lots of vertices, just - they're called isolated vertices that start no edges. So this has a million billion gazillion vertices and ten edges. And you can't embed it. Because it's got this K5 that you have to embed. And you can say, well this is just a cheat and - disconnected graphs. But make it connected. Put maybe let's call the pass. Or the thing like this that goes through all of these vertices.
- (Brady: I would argue that's still bit of a cheat) (but, alright)
- I mean this may be a way to make it sufficiently connected and - If you'd like to watch even more from this interview where we go into the professor's work on so-called perfect graphs, then we've put that over on Numberphile2, our second channel. There'll be links on the screen and down in the video description
Enjoyed the “still untitled” podcast, but this one will have to wait until after the drive!