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.
