WEBVTT
00:00:04.080 --> 00:00:08.200
In my video on the circle division problem, I referenced Euler’s characteristic formula.
00:00:08.600 --> 00:00:11.960
And here, I would like to share a particularly nice proof of this fact.
00:00:12.600 --> 00:00:20.040
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.
00:00:20.600 --> 00:00:27.760
Instead, I chose this topic to illustrate one example of the incredible notion of duality and how it can produce wonderfully elegant math.
00:00:28.920 --> 00:00:31.160
First, let’s go over what the theorem states.
00:00:31.760 --> 00:00:53.200
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.
00:00:54.360 --> 00:01:08.640
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.
00:01:08.640 --> 00:01:14.960
Hence, we write Euler’s discovery as 𝑉 minus 𝐸 plus 𝐹 equals two.
00:01:14.960 --> 00:01:22.040
Before describing the proof, I need to go through three pieces of graph theory terminology: cycles, spanning trees, and dual graphs.
00:01:22.720 --> 00:01:29.360
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.
00:01:30.680 --> 00:01:33.280
Imagine a tiny creature sitting on one of the vertices.
00:01:33.720 --> 00:01:34.480
Let’s name him Randolph.
00:01:35.360 --> 00:01:47.320
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.
00:01:49.280 --> 00:01:53.000
A cycle is simply a path that ends on the same vertex where it begins.
00:01:53.200 --> 00:02:00.000
You might be able to guess how cycles will be important for our purposes, since they will always enclose a set of faces.
00:02:01.240 --> 00:02:10.880
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.
00:02:11.520 --> 00:02:18.560
This frugality will leave him with a set of edges without any cycles, since the edge finishing off a cycle would always be unnecessary.
00:02:18.560 --> 00:02:34.360
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.
00:02:35.760 --> 00:02:43.200
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.
00:02:43.720 --> 00:02:55.080
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.
00:02:55.680 --> 00:03:01.760
For instance, Facebook stores an enormous graph, where vertices are accounts and edges are friendships.
00:03:02.400 --> 00:03:10.200
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.
00:03:11.240 --> 00:03:37.680
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.
00:03:38.640 --> 00:03:52.880
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.
00:03:53.680 --> 00:03:56.120
We call this the dual of the original graph.
00:03:57.120 --> 00:04:03.160
If you want to represent the dual graph with dots and lines, first put a dot inside each one of the faces.
00:04:03.840 --> 00:04:12.200
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.
00:04:12.200 --> 00:04:25.160
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.
00:04:26.040 --> 00:04:39.280
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.
00:04:40.160 --> 00:04:48.080
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.
00:04:49.160 --> 00:04:55.040
You see, what makes the dual graph all kinds of awesome is the many ways that it relates to the original graph.
00:04:55.600 --> 00:05:07.040
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.
00:05:08.280 --> 00:05:09.320
Now for the cool part.
00:05:09.720 --> 00:05:19.600
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.
00:05:20.400 --> 00:05:26.520
Let’s say Randolph has bought all the edges of a spanning tree and that Mortimer is forbidden from crossing those edges.
00:05:27.320 --> 00:05:34.520
It turns out the edges that Mortimer has available to him are guaranteed to form a spanning tree of the dual graph.
00:05:36.600 --> 00:05:46.200
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.
00:05:49.000 --> 00:05:58.280
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.
00:06:00.960 --> 00:06:05.360
The reason Mortimer cannot traverse a cycle in the dual graph feels completely symmetric.
00:06:06.000 --> 00:06:13.640
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.
00:06:13.640 --> 00:06:26.520
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.
00:06:28.360 --> 00:06:34.080
Here’s the kicker: the number of vertices in any tree is always one more than the number of edges.
00:06:35.560 --> 00:06:42.000
To see this, note that, after you start with the root vertex, each new edge gives exactly one new vertex.
00:06:42.520 --> 00:06:53.000
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.
00:06:53.760 --> 00:07:00.520
Since this tree covers all vertices in our graph, the number of vertices is one more than the number of edges owned by Randolph.
00:07:01.240 --> 00:07:12.600
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.
00:07:13.440 --> 00:07:22.080
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.