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 \chi = v - e\ . We can show, for example, that every tree (a graph with no closed paths) has \chi = 1\ . 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.

k4-a

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-b

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 \chi = 4 - 6 = -2\ .

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:

\chi = v - e + f = 2\

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

2\ e \ge 3\ f\ \text{or } 2\ e \ge 4\ f 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 \chi = 2 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 2\ e \ge 3\ f\ . 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:

k5

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 \chi = 2\ , 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 2\ e \ge 3\ f\ .

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:

k33

Let’s check the same inequality, 2\ e \ge 3\ f\ . 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:

2\ e = 18 \ge 15 = 3\ f\ .

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

2\ e \ge 4\ f\ .

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

2\ e = 3\ f_3 + 4\ f_4 + 5\ f_5 + ...

where f_i is the number of faces having i edges.

Now set f3 = 0, and replace i f_i\ \text{by the smaller } 4 f_i\ :

2\ e \ge 4\ f_4 + 4\ f_5 + 4\ f_6 + ... = 4 f

since f = \Sigma f_i.\ )

So we compute

2 e = 18 < 20 = 4 f,

instead of 2\ e \ge 4\ f\ ,

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

2\ e \ge 4\ f - 1\ .

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

2\ e \ge 3\ f\ .

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 2\ e \ge 3\ f\ ; and also that K3,3 is nonplanar because it violates 2\ e \ge 4\ f\ . 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 2\ e \ge 3\ f\ , and they leave K3,3 to the exercises, without a hint.

About these ads

2 Responses to “Nonplanar graphs & the Euler characteristic”

  1. Robin Says:

    Nice – just what I needed to fill in a blank at http://www.theoremoftheday.org/Theorems.html#24.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 46 other followers

%d bloggers like this: