Euler’s Theorem of Planar Graphs

It is one of the most beautiful idea of mathematics. Indeed, David Richeson has written a new book in which he calls the theorem "Euler's Gem", and truly it is. You can see the book, and order it,here.


I wrote this a while back, but wanted to post it again because it popped up in class the other day....kids do NOT seem to know this great idea. So here is an old post about an even older idea that is way too important to ignore in any class... go in tomorrow and forget whatever else you were gonna teach, and take 20 minutes and introuduce it...
-------------------------------------------------------------
Euler was such a prolific mathematician that there are many theorems that bare the name “Euler’s Theorem.” In this short article I will sometimes say “Euler’s Theorem” when I mean the particular theorem that shows that for all connected planar graphs (on a plane or a sphere), the number of vertices, v; edges, e; and faces f; obey the simple relationship v+f=e+2.

Student’s are often introduced to Euler’s Theorem as early as seventh or eighth grade, but almost always in a way that leads them to intuit the result. They are seldom shown, or asked for, a proof of the theorem. Since it forms the foundation for the proof of several other topics that students are introduced to in discrete math classes, I wanted to illustrate one proof here that I believe is understandable to most high school students.
Euler’s Theorem is directly applicable to graphs drawn on a sphere, and that is, perhaps, the best reason to provide to students for the question “Why do we count the face outside the boundary edges?”

We begin with a simple statement that is easy to prove. All connected trees meet Euler’s Theorem. First, since there are no cycles in a tree, the total number of faces is one, f=1. Now start with a single vertex and no edges (perhaps we call this the “seed” of a tree, or a proto-tree. There is one face, one vertex, and no edges, so clearly v+f=e+2 is satisfied.

Now what do we do to make the tree more complex? Well, we add edges; but each new edge begins at some existing vertex, already counted, and extends to some new vertex not yet counted, thus increasing edges and vertices by one and continuing. If the edge went between two existing vertices it would complete a cycle. So if we add n edges, we have to add n vertices to connect them to, and there is still only a single face. For a connected tree, then, it is always true that v=e+1 and f=1 and so v + f = e+1 + 1 = e+2 and the theorem is confirmed again.

But Euler’s Thm is NOT about trees, it is about all planar graphs and they might, and usually do, have cycles. Next we just show that any planar graph can be pruned to make it a tree without changing the relationship between edges and faces.

In the figure at right we show a planar graph with six vertices, three faces and some edges (we ignore how many for now). Pick any of the edges and remove it. What did you do to the number of faces? What did you do to the number of edges? Now continue to remove an edge that is part of a cycle. The net result is a simple connected tree for which with one face, v vertices, and v-1 edges (because it is a tree). If we removed n edges from the original graph, then we must have removed n faces, and so the original graph had 1+n faces, v vertices, and v-1+n edges. We check to be sure, and v+(1+n) = (v-1+n) +2 and simplifying we see that Euler’s theorem is also true for the original graph. But since any such planar graph can be reduced to a connected tree by the same method, then all planar graphs obey Euler’s Theorem for Planar Graphs.