A Proof of Euler’s Formula Using Graph Duality

I want to show a proof of Euler’s characteristic formula that illustrates the elegance of duality. This is not a claim that the proof is better than the usual inductive one; it is an example of how a different perspective can reveal structure.

Draw a connected graph in the plane without crossing edges. Count its vertices V, its edges E and the faces F into which those edges divide the plane, including the unbounded outer face. Euler’s formula says V − E + F = 2. The terminology comes from Euler’s original work on three-dimensional polyhedra.

Imagine a creature named Randolph traveling along the graph’s edges. A path is a sequence of edges he can travel without immediately retracing an edge; a cycle returns to its starting vertex. Cycles matter here because they enclose faces.

Now suppose Randolph wants to reach every vertex, but buys an edge only when it gives him access to a vertex he could not reach before. He ends up with a connected set of edges without cycles: a tree. A tree that touches every vertex of the original graph is called a spanning tree.

A graph itself is more abstract than its drawing: it consists of objects and a notion of connection. Accounts and friendships form a graph, as do words linked when they differ by one letter or mathematicians linked by coauthored papers. Dots and lines are a way to depict those relationships.

For a planar drawing, consider each face an object and say two faces are connected across an edge. This produces the dual graph. To draw it, place a vertex in each face and connect vertices across the original edges. The outer face also gets a vertex, which can be pictured as a point at infinity; multiple edges and loops can occur in the dual.

The distinction between a graph and its drawing helps make the correspondence clear: each original edge has a dual edge, even though their drawn lines look different. Cycles and separation in one graph are related to connectivity in the other.

Give Randolph an alter ego, Mortimer, who travels between faces in the dual. Randolph owns the edges of a spanning tree, and Mortimer may cross only the remaining edges. Those remaining edges form a spanning tree of the dual: they connect all faces and contain no dual cycle.

Why can Mortimer reach every face? A collection of Randolph’s edges could trap a face only by forming a cycle, which a tree cannot have. Conversely, if Mortimer could follow a dual cycle, it would separate some original vertices from the others, contradicting the fact that Randolph’s tree spans all vertices.

A tree with V vertices has V − 1 edges: after the first vertex, each new edge brings in one new vertex. Randolph’s tree therefore uses V − 1 edges. Mortimer’s tree spans the F faces of the original graph, so it uses F − 1 of the remaining edges. Together they account for every original edge: E = (V − 1) + (F − 1), or V − E + F = 2.