Graphs and Donuts

I think I wrote a couple posts ago that I would post something about some stuff that I am fooling around with in a mental sense, so I will do that.

I came across a book about Topological Graph theory and since that sounded good and weird and like I wouldn't need to find a bunch of inequalities to do it, I started reading it, and came upon a problem involving planar graphs. A little explanation, though not anything rigorous:

First you have to know what a graph is. It is essentially a set of points connected by line segments. The points are called vertices, and the segments are called edges. Technically, graphs are sets which contain two sets, an edge set and a vertex set, where the vertex set is basically single numbers (generally integers), and edges are pairs of numbers, where both of the integers in the pair appear in the vertex set. But for our purposes, they are just dots with lines connecting them.

For most purposes, simple graphs will suffice, which are graphs where only one edge can appear between any two vertices, and no edge can connect a vertex to itself. If you are inclined to chemistry, you can think of them as molecule diagrams where no double bonds are allowed, but any number of bonds can be made between atoms. Actually, there is an interesting problem in graph theory of counting isomers of carbon chains of arbitrary length, but I digress.

The next thing you have to understand is what is meant by planar graphs. A planar graph is a graph that can be drawn in the plane without any edges intersecting. The analyst in my office would complain about that definition, but my tensor professor would love it because he insists that "R^2 is not a plane; a plane is a plane. R^2 is a set of pairs of numbers. What is a plane? I can't tell you, but I know what it is." That isn't an exact quote, but it is close. He also says things like, "There's no such thing as integration by parts. There is only the product rule." (^_^)

I will now give examples, like a good textbook:



This graph is K4 (the 4 is supposed to be a subscript, but blogs...). That is shorthand for the complete graph on four vertices, meaning that it has every edge that can exist on four vertices. Exercise: how many edges does Kn (the complete graph on n vertices) have?

Is K4 planar? One is tempted to say "no," since those two edges in the box intersect, and that's a no-no according to our definition. However, what if we draw it like this:



Now we have the same graph drawn in the plane, with no edges intersecting, so the answer above should actually be "yes." Technically, these graphs are not the same, they are only "isomorphic," but all that means is that if you treat graphs as they should be treated, as sets, and make a renaming function (i.e., an isomorphism) between the sets, all the relationships are preserved.

A better question is what graphs are (not) planar? A dude named Kuratowski essentially answered that question all at once and very neatly. He said (and proved) that all the non-planar graphs contain a copy of K5 or K3,3 (the bipartite graph on 3 and 3 vertices; a picture will follow). Technically, they just have to contain a subdivision of one of these two graphs. That is, if you take one of those graphs and add vertices on already established edges, you also can't draw that on the plane, but the important point is that we can tell, in a certain sense, very easily if a graph can be drawn in the plane.

K5



K3,3



The second one is called the complete bipartite graph because it has two subsets of vertices {1,2,3} and {4,5,6} that have no edges inside them, but all the other edges are there.

So, how do we know that things are planar/not planar? To show that something is planar, it's easy enough to just draw it in the plane, though in practice this could be staggeringly difficult for large graphs. To show something is non-planar, you can't just show one non-planar representation; you have to show that no planar representation is possible. Here's a bare-bones proof that K5 is non-planar, using the concept that that previous planar representation of K4 is "unique" up to bending, stretching and renaming, none of which affects planarity.



Now try putting the fifth vertex in any of the regions we've created and see if you can draw an edge to all the other vertices. So K5 isn't planar! I'll leave a proof of K3,3 up to you, but it can be done in much the same way.

Now, a mind that likes puzzles might wonder what is so special about the plane? What about other shapes, like a ball? Well, that question has been asked, but not totally answered. From now on I'm going to call "shapes" "surfaces" because that is the actual term. I'm not going to give you a real definition of a surface, but it essentially boils down to adding loops and crosscaps to the sphere.

The first part of the question is are there "planar" graphs and "non-planar" graphs for other surfaces, and the first answer is yes. In fact, some dude showed that for any surfaces, there is a finite set like {K5, K3,3} that generates all the non-embeddable graphs. However, except for the sphere, nobody knows what they are, so that is what I am messing with, but it is pretty complex. Let's consider the sphere:



There's our good buddy K4 drawn on the surface of a sphere. It shouldn't come as a surprise that anything we can embed on a plane we can embed on a sphere, since a sphere is what's called "locally Euclidean;" it looks like a plane as long as you only look in a little disk. But is that drawing still unique, as it was in the plane?



Oh, ho, ho! What if we wrap the last edge around the back? Well, it turns out that that doesn't change anything at all, because wrapping around the back is the same as stretching back and back and back. So, well, the sphere isn't too interesting. It's the same as a plane, but we like to use a sphere to judge from because it's what's called "compact." Don't worry about that much.

So what's the next simplest thing? A doughnut, or donut to normal people. Mathematicians of course call it a torus because we are contrarians by nature. Let's try drawing K4 again:



Try and draw the fifth vertex and you'll run into the same problem as before. But does this mean that K5 is non-embeddable on the torus? You should know by now that that isn't the case. What if we start by drawing the box in more natural ways?





Now try to draw that fifth vertex and you'll find that not only can you draw K5, but you can draw it in more than one way! So a donut has a little more freedom than a ball.

So, I'm not really sure which graphs can and can't be embedded yet, but I've managed to embed K5 but not K6 on the torus, as well as K3,4. I don't know if I embedded K4,4 yet, as I have tons of scrap paper with drawings on them now. Anyway, that's what I've been up to.