Nonplanar graphs & the Euler characteristic

Introduction and K4, the complete graph on 4 vertices

I want to show you something clever, but I’m going to omit the details of how we justify part of it. And I’m going to raise a question about another part of it. But I think this application of the Euler characteristic is interesting, even if I won’t or can’t cross all the t’s.

We can define the Euler characteristic of a graph as . We can show, for example, that every tree (a graph with no closed paths) has . If a graph is not a tree, then the closed path might create a face, but we don’t count the faces.

One question that arises when we have a graph is: is the graph planar? That is, can it be drawn in the plane so that edges do not have extraneous intersections?

Better to show you. Draw a square (or rectangle), and draw the two diagonals. This is called K4, the complete graph on 4 vertices, because every vertex is connected to every other vertex.

But the diagonals cross each other.

But they don’t have to. Take one of them and stretch it, and pull it outside the square.

K4 is called a planar graph, because its edges can be laid out in the plane so that they do not cross. I might say that it’s manifestly planar. Its Euler characteristic is .

Although it has 3 faces, we aren’t counting them. (OTOH, it’s not an accident that it has 3 faces and its Euler characteristic is 1 – 3; I think each loop added to a tree subtracts 1 from the Euler characteristic.)

Now, the theorem I’m not going to prove (even Firby & Gardiner don’t prove all of it), is that if we embed a planar graph onto the sphere, and then count faces created by the embedding, the embedded graph has the Euler characteristic of the sphere:

We’re going to almost show that a couple of graphs cannot be planar; we will use to compute the number of faces created by the embedding, and we will show that either

is false.

Got that? I’m not going to prove that the Euler characteristic of the embedded graph is 2, but I’m going to use that result to compute the number of faces of a planar graph.

Why do I say embedding? Let’s look at K4, the square with diagonals: we have v = 4, e = 6, and we infer from that the embedded graph has 4 faces.

But when we drew the graph, it had 3 faces. Ah, but on the sphere there’s all the rest of the sphere, the “ocean” if you will. Note that the “ocean” touches 3 edges when I draw the graph so that it is manifestly planar. We’ve added a face when we embed the graph on the sphere.

So the Euler characteristic of a graph doesn’t count any faces; the Euler characteristic of a graph embedded on a surface does count faces.

Just for the fun of it: for K4, 2 e = 12, 3 f = 12, and we do have . In fact we have equality because every face has exactly 3 edges.

K5, the complete graph on 5 vertices

That was K4. Here is K5, i.e. 5 vertices and they’re each connected once to every other vertex:

Is it planar?

Embed it on the sphere. We have 5 vertices by definition, and (1/2) (5) (4) = 10 edges (“5 choose 2, order doesn’t matter”) From the Euler characteristic , we infer that the embedded graph has 7 faces. To be clear, if the graph K5 is planar, then the embedded graph has Euler characteristic 2 and 7 faces.

But we have

2 e = 20

and 3 f = 21,

and therefore 2 e < 3 f instead of .

We conclude that K5 cannot be planar.

(That inequality assumes that very face has at least 3 edges. Well, it can’t very well be a face with only 2 edges, can it? Can it?)

K3,3, the complete bipartite graph on 3 & 3 vertices

What about K3,3, the complete bipartite graph on 3 & 3 vertices? This is also called the utilities graph: we may imagine we have 3 utilities (gas, water, electric) and 3 houses, and every house needs to be connected to every utility. It’s called bipartite because there are two disjoint subsets of vertices, and all the vertices in one subset are connected to all the vertices in the second subset (and vice versa).

Is it planar? Can we lay out the utilities all on one level without the lines bumping into each other? (Of course, my electricity comes in on overhead wires, but in principle the town could have required that the electric line be underground, as the gas and water are.)

Here’s the graph:

Let’s check the same inequality, . We have 6 vertices and 9 edges. If the graph K3,3 is planar, then the embedded graph has Euler characteristic 2 and 5 faces… then 2e is 18, and 3f is 15, and the inequality is satisfied:

.

That tells us nothing.

Let’s think about it some more. Start at a vertex (“a”), follow an edge to a vertex (“b”) (which must be on the “other side”). If we return on the same edge, we don’t get a face. If we return on a different edge, we end up at a different vertex “c”. To get back to “a”, we have to go to the other side and back again.

That is, each face (except possible the “ocean”) has at least 4 edges. Let’s not worry about the ocean for now. If f3 = 0 (“no faces have 3 edges”), then we can show that

.

(The key is that every edge must separate two faces; then if every face has at least three edges,

where is the number of faces having i edges.

Now set f3 = 0, and replace :

since )

So we compute

2 e = 18 < 20 = 4 f,

instead of ,

and we conclude that K3,3 is not planar… except that we really need to argue that the ocean touches at least 4 edges.

Do we? If we suppose the ocean only touches 3 edges (i.e. f3 = 1), we can show that

.

But, instead, we have

2 e = 18 < 19 = 4 f – 1.

We still have a contradiction, so K3,3 is not planar.

It turns out, that’s all folks. Kuratowski’s theorem (1930) says that a graph is not planar if and only if it contains K5 or K3,3. They are the “atoms” of nonplanar graphs; at least one of them is contained in every nonplanar graph.

a distressing observation

Having done that, let me back up and confuse you. Let me show you the t’s I’m not crossing. (In addition to not proving that the Euler characteristic of the graph embedded on the sphere is 2.)

Let’s take a planar graph with 2 vertices and 1 edge, i.e. a single line segment. It’s the tree with 2 vertices. Embed it on the sphere, and infer that it has one face.

The ocean.

Which touches one edge.

Now, the ocean really seems to be a face, i.e. a 2D thing. But it only has 1 edge. Grrr. Did you believe me when I said that something couldn’t be a face if it only had two edges? That’s OK, I believed me, too.

Oh, don’t seriously think of checking

.

That came from the assumptions that every face has at least 3 edges (false), and every edge touches 2 faces (false, but close: in this case our single edge does have “ocean” on both sides).

We could also take a tree on 3 vertices, i.e. the previous graph with a vertex added inside the edge. Embed it on the sphere. Now we have 2 edges, 3 vertices, and we compute that it has 1 face, and that face touches all 3 vertices and both edges. But that face does not have 3 edges. I mention this case because the books limit the original theorem (“the Euler characteristic of a planar graph embedded on the sphere is 2″) to graphs with at least 3 vertices, which seems to include this case.

My objection in both of these cases is that the ocean is not a nice face. What we have not done for K5 or K3,3 is to show that there isn’t some weird shape of ocean that makes them planar but does not force the inequalities which we know are false.

Clearly, we would have to do some more work to make all of this hang together properly. What we’ve got is two really nice plausibility arguments that K5 and K3,3 are not planar.

When I check the graph theory books, they all seem to sail right past the number of edges on the ocean, and the requirement that every edge separates two faces. (Again, for these two trees, each edge does have a face on each side, but it’s the same face!)

References

Every one of the four graph theory books in the bibliography (Bollobas, both Bondy & Murty books, and Biggs, et al.) proves that K5 is nonplanar because it violates ; and also that K3,3 is nonplanar because it violates . Only Bollobas does not prove Kuratowski’s theorem. Biggs et al. contains Kuratowski’s paper.

Both Bondy & Murty books also prove that K5 and K3,3 are nonplanar because they violate the Jordan Curve theorem.

Finally, Firby & Gardiner, and Sieradski, prove that K5 is nonplanar because it violates , and they leave K3,3 to the exercises, without a hint.

Books Added 1 Aug 2008: Graph Theory

I have had a long-standing question: why is the usual triangulation of a torus so large? It is a square with 18 triangles. Why so many?

While looking through algebraic topology books for more information about simplicial complexes – which is supplementary material for Bloch (“A First Course in Geometric Topology….” – I found the answer. Well, I found a clue. I found an inequality, which implied that the minimum number of triangles was 14 in any possible triangulation of the torus.

What I didn’t find was a proof of that inequality, and I couldn’t work it out for myself.

Eventually, in another algebraic topology book, I found another clue, and it was enough to let me work out the first inequality.

Along the way I found some pretty interesting things, and I want to chatter about them. The result will not really be math, but more in the nature of a travel guide.

Well, no, not even that detailed. More in the nature of some really cool pictures from a foreign country.

The search took me into both algebraic topology and graph theory. Before I put out the posts (there will be at least two), I need to put out some bibliography.

The graph theory is easy. I only own 4 books on graph theory, and I acquired one of them just this week.

So, the following books on graph theory have been added to the bibliography.

There are two old classics. Biggs et al. is a collection of 37 original papers that helped found graph theory. Where necessary, they have been translated into English, and the authors have written whatever introductory material was necessary before each paper.

Here you will find Euler’s foundational paper on the Konigsberg bridges, of course; but also Kirchhoff’s paper using graph theory for electric circuits. (Yes, the use of graphs for simplifying the application of Kirchhoff’s laws goes back to Kirchhoff himself!)

Among other things you will find Euler’s polyhedral formula (V – E + F = 2), chemical graphs, the four-color problem, and planar graphs.

The other old classic is Bondy & Murty “Graph Theory with Applications”. Every chapter ends with “Applications”. I like that. In fact I would be unhappy without them.

I love the terminology of graph theory: an acyclic graph is also called a forest; each component is called a tree (so a tree is a connected acyclic graph). But after a while I begin to feel like I’m just proving random facts about random things. I’d like to do better.

The other two books? One is a brand new book by Bondy & Murty. They say in the introduction that it began as a second edition. It grew too much, and the different title reflects that growth. (It wouldn’t have been the first “second edition” to be a different book.)

Realistically speaking, I could have mentioned the book, said I didn’t own it, and left it up to you to decide whether to buy it. OTOH, if I try to order it myself and find that you all have exhausted Amazon’s supply… well, that would be terrible.

I just had to buy the book. (That happens a lot, for one reason or another.)

It is a much larger book than it’s predecessor. (Have I ever seen a second edition smaller than the first? Only when the book split into multiple volumes.) It still contains applications, but you’ll find them listed under “problems” in the index. OTOH, you’ll also find a detailed sublist of “proof techniques” in the index. I think that’s way cool. (You will find elementary techniques such as induction and contradiction, intermediate techniques such as the pigeonhole principle, as well as techniques specific to graph theory.)

The book can be used as an undergraduate text: just read the first few sections of most of the chapters; or as a graduate text: read it all!

One major caveat: there is a second printing under way. According to the web site (here) it will, of course, correct errata, but it will also be “slightly reorganized”. I’m not sure what that bodes, but you might want to wait for the second printing.

Finally, I have a book by Bollobas. I can tell from the price sticker that I bought it during a Springer “yellow sale” in 2003, for about 1/3 off. I am sure I bought it just because I wanted a more modern book than the old classics.

I have no regrets. Quite the contrary. The first chapter, fundamentals, is a rather compact presentation: graphs, trees, Euler & Hamiltonian cycles, and planar graphs. Whew! But it’s well written, and it’s nice to have what amounts to: if I only get to show you one chapter of graph theory, well here it is.

The second chapter is electrical networks. Good, we have some applications.

But then section 2 of the second chapter uses electrical networks to search for “squared squares” and “squared rectangles”. Hey what? An example of a squared rectangle is the following (where each integer is the length of a side of the square in which it sits, and the whole thing is a 33×32 rectangle):

I know some of those! I played with them several years ago.

I am looking forward to Bollobas.

I’m getting excited about doing graph theory. I’m pretty sure I’ll go through the old Bondy & Murty first, but with the history book handy. (If I didn’t have the old Bondy & Murty, I would work the first few sections of each chapter of the new one. Having the old one, I view the new one as a reference book. Perhaps I’m wrong to do that.)

After I had worked both of those, I would hit Bollobas.

Or maybe I’ll do the first chapter of Bollobas, and then the other two….

I’ll let you know.

Bollobas, Bela. Modern Graph Theory. Springer, corrected printing 2002.
ISBN 0 387 98488 7.
[graph theory;1 Aug 2008]
“Graduate Texts in Mathematics”. I haven’t worked thru it yet, but its first two chapters look spectacular, and it has lots of exercises. The first chapter is an introductory overview, possible because we can get powerful theorems early on. The second chapter is a delightful looking digression on electrical networks and subdivisions of rectangles.

Bondy, J.A. and Murty, U.S.R. Graph Theory with Applications. North Holland, 1976.
ISBN 0 444 19451 7.
[graph theory;1 Aug 2008]
This is the old classic. Every chapter ends with applications. Just looking thu it makes me want to curl up and work thru it.

Bondy, J.A. and Murty, U.S.R. Graph Theory. Springer, 2008.
ISBN 978 1 84628 969 9.
[graph theory;1 Aug 2008]
“Graduate Texts in Mathematics”. Looks as though it could be used as an undergraduate text, or as a second-year graduate text getting one ready for research; just decide how far into each chapter to read.

Biggs, Norman L, Lloyd; E. Keith; Wilson, Robin J. Graph Theory 1736–1936.
ISBN 0 19 853901 0.
[graph theory;1 Aug 2008]
This seems a very gentle introduction, although it does have proofs. It’s a collection of the original papers about graph theory – translated into english, with substantial commentary before each.