A Proof of Euler’s Formula Using Graph Duality

ZUSAMMENFASSUNG

In 30 Sekunden

3Blue1Brown explains cycles, spanning trees and planar duals before using their relationship to prove Euler’s formula for a connected planar graph. The key is that the edges outside a spanning tree form a spanning tree of the dual.

1Euler’s characteristicFor a connected planar drawing, V − E + F = 2 when the outer face is included.
2Spanning treesA spanning tree connects all vertices without cycles, using V − 1 edges.
3The dual graphTreat faces as vertices and connect the faces on either side of each original edge.
4Complementary treesThe edges not in the original spanning tree form a spanning tree of the dual.
5Count the edgesThe two trees have V − 1 and F − 1 edges, so E = V + F − 2.

Das Wichtigste

For a connected planar graph, vertices minus edges plus faces equals two, including the unbounded face.
A spanning tree connects every vertex without forming a cycle.
The dual graph has one vertex for each face of the original embedding and a corresponding edge across each original edge.
The edges outside a primal spanning tree form a spanning tree in the dual, so their counts yield Euler’s formula.

ThemenMathematics Science Communication

VOLLTEXT

Den bearbeiteten Text nach Kapiteln lesen

Transkript zeigen

Nur das Transkript

Euler’s formula and graph terminology

The formula relates vertices, edges and faces of a connected planar graph. Cycles and spanning trees provide the tools for the proof.

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.

FOLIE 1 / 4Vertices, edges and facesA connected planar graph illustrates the quantities in Euler’s formula.

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.

Constructing the dual graph

A graph is an abstract set of objects and connections. For a planar embedding, its faces become the vertices of a dual graph.

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.

FOLIE 2 / 4The planar dualThe red dual edges cross the original graph’s edges and connect its faces.

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.

Two spanning trees and the edge count

The edges outside a spanning tree form a dual spanning tree. Counting both trees proves Euler’s formula.

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.

FOLIE 3 / 4A dual cycle would separate verticesThe diagram illustrates why a cycle available to Mortimer would prevent the original spanning tree from connecting every vertex.

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.