Video: Euler’s Formula and Graph Duality

Grant Sanderson • 3Blue1Brown • Boclips

Euler’s Formula and Graph Duality

07:26

Video Transcript

In my video on the circle division problem, I referenced Euler’s characteristic formula. And here, I would like to share a particularly nice proof of this fact. It’s very different from the inductive proof typically given, but I’m not trying to argue that this is somehow better or easier to understand than other proofs. Instead, I chose this topic to illustrate one example of the incredible notion of duality and how it can produce wonderfully elegant math.

First, let’s go over what the theorem states. If you draw some dots and some lines between them, that is, a graph, and if none of these lines intersect, which is to say you have a planar graph, and if your drawing is connected, then Euler’s formula tells us that the number of dots minus the number of lines plus the number of regions these lines cut the plane into, including that outer region, will always be two.

Because Euler was originally talking about 3D polyhedra when he found this formula, which was only later reframed in terms of planar graphs, instead of saying dots, we say vertices; instead of saying lines, we say edges; and instead of saying regions, we say faces. Hence, we write Euler’s discovery as 𝑉 minus 𝐸 plus 𝐹 equals two.

Before describing the proof, I need to go through three pieces of graph theory terminology: cycles, spanning trees, and dual graphs. If you are already familiar with some of these topics and don’t care to see how I describe them, feel free to click the appropriate annotation and skip ahead.

Imagine a tiny creature sitting on one of the vertices. Let’s name him Randolph. If we think of edges as something Randolph might travel along, from one vertex to the next, we can sensibly talk about a “path” as being a sequence of edges that Randolph could travel along, where we don’t allow him to back-track on the same edge.

A cycle is simply a path that ends on the same vertex where it begins. You might be able to guess how cycles will be important for our purposes, since they will always enclose a set of faces.

Now imagine that Randolph wants access to all other vertices, but edges are expensive, so he’ll only buy access to an edge if it gives him a path to an untouched vertex. This frugality will leave him with a set of edges without any cycles, since the edge finishing off a cycle would always be unnecessary.

In general, a connected graph without cycles is called a tree, so named because we can move things around and make it look like a system of branches, and any tree inside a graph which touches all the vertices is called a spanning tree.

Before defining the dual graph, which runs the risk of being confusing, it’s important to remember why people actually care about graphs in the first place.

I was actually lying earlier when I said a graph is a set of dots and lines; really it’s a set of anything with any notion of connection, but we typically represent those things with dots and those connections with lines.

For instance, Facebook stores an enormous graph, where vertices are accounts and edges are friendships. Although we could use drawings to represent this graph, the graph itself is the abstract set of accounts and friendships, completely distinct from the drawing.

All sorts of things are undrawn graphs: the set of English words, considered connected when they differ by one letter; mathematicians, considered connected if they’ve written a paper together; neurons connected by synapses, or, maybe, for those of us reasoning about the actual drawing of a graph on the plane, we can take the set of faces this graph cuts the plane into and consider two of them connected if they share an edge.

In other words, if you can draw a graph on the plane without intersecting edges, you automatically get a second, as of yet, undrawn graph, whose vertices are the faces and whose edges are, well, edges of the original graph. We call this the dual of the original graph.

If you want to represent the dual graph with dots and lines, first put a dot inside each one of the faces. I personally like to visualize the dot for that outer region as being a point somewhere at infinity, where you can travel in any direction to get there.

Next, connect these new dots with new lines that pass through the centers of the old lines, where lines connected to the point at infinity can go off the screen in any direction, as long as it’s understood that they all meet up at the same one point.

But keep in mind this is just a drawing of the dual graph, just like the representation of Facebook accounts and friendships with dots and lines is just a drawing of the social graph; the dual graph itself is the collection of faces and edges.

The reason I stress this point is to emphasize that edges of the original graph and edges of the dual graph are not just related; they’re the same thing.

You see, what makes the dual graph all kinds of awesome is the many ways that it relates to the original graph. For example, cycles in the original graph correspond to connected components of the dual graph, and likewise cycles in the dual graph correspond with connected components in the original graph.

Now for the cool part. Suppose our friend Randolph has an alter ego, Mortimer, living in the dual graph, traveling from face to face instead of from vertex to vertex, passing over edges as he does so.

Let’s say Randolph has bought all the edges of a spanning tree and that Mortimer is forbidden from crossing those edges. It turns out the edges that Mortimer has available to him are guaranteed to form a spanning tree of the dual graph.

To see why, we only need to check the two defining properties of spanning trees: they must give Mortimer access to all faces and there can be no cycles.

The reason he still has access to all faces is that it would take a cycle in Randolph’s spanning tree to insulate him from a face, but trees cannot have cycles.

The reason Mortimer cannot traverse a cycle in the dual graph feels completely symmetric. If he could, he would separate one set of Randolph’s vertices from the rest, so the spanning tree from which he is banned could not have spanned the whole graph.

So not only does the planar graph have a dual graph, any spanning tree within that graph always has a dual spanning tree in the dual graph.

Here’s the kicker: the number of vertices in any tree is always one more than the number of edges. To see this, note that, after you start with the root vertex, each new edge gives exactly one new vertex.

Alternatively, within our narrative, you could think of Randolph as starting with one vertex and gaining exactly one more for each edge that he buys in what will become a spanning tree. Since this tree covers all vertices in our graph, the number of vertices is one more than the number of edges owned by Randolph.

Moreover, since the remaining edges make up a spanning tree for Mortimer’s dual graph, the number of edges he gets is one more than the number of vertices in the dual graph, which are faces of the original graph.

Putting this together, it means the total number of edges is two more than the number of vertices plus the number of faces, which is exactly what Euler’s formula states.

Nagwa uses cookies to ensure you get the best experience on our website. Learn more about our Privacy Policy.