This 1963 paper by W. T. Tutte is a cornerstone of enumerative combinatorics. It provides the first exact formulas for counting various classes of planar maps—graphs drawn on a sphere or plane such that no edges cross. By introducing the clever technique of "rooting," Tutte transformed a messy problem of symmetry into an elegant exercise in generating functions and functional equations.
TL;DR
Tutte solves the long-standing problem of counting distinct planar maps by "rooting" them to eliminate symmetry. He derives exact closed-form and recursive formulas for general, non-separable, and 3-connected maps, laying the groundwork for modern enumerative graph theory.
What Problem Does This Paper Address?
In the mid-20th century, mathematicians struggled to count how many "different" ways a graph could be embedded in a plane. The primary obstacle was symmetry. For example, if you rotate a square map 90 degrees, is it a "new" map or the same one? Standard counting methods often overcounted these symmetric variations.
Tutte’s "Census" series (this being the fourth installment) aimed to build a rigorous theory for counting these structures. The goal was to find exact formulas for the number of maps with $n$ edges, categorized by their connectivity (e.g., general maps vs. non-separable maps).
Methods
The paper’s breakthrough relies on several key mathematical strategies:
- Rooting: Tutte defines a "rooted" map by picking one edge as the root, assigning it a direction, and specifying a "left" and "right" side. This simple act "breaks" the symmetry of the map. Because a rooted map has no non-trivial automorphisms (symmetries that preserve the root), counting them becomes a purely combinatorial task.
- First Derived Maps: Tutte uses a construction (similar to barycentric subdivision) to transform any map into a "triangular" map where every face is a triangle. This allows for a unified treatment of vertices, edges, and faces.
- Functional Equations: He sets up equations where the unknown is a power series (a generating function) whose coefficients are the numbers he wants to find. For example, he relates the generating function for general maps $A(x)$ to that of non-separable maps $B(x)$ through equations like $A(x) = B(x\{1 + A(x)\}^2)$.
- Lagrange’s Inversion Theorem: This is the "heavy lifting" tool used to solve these functional equations and extract the exact coefficients (the counts) from the power series.
Datasets
Not discussed in the paper. As a theoretical mathematics paper, it relies on logical proof and derivation rather than empirical data or benchmarks.
Key Insights and Ideas
- Symmetry is the Enemy: The most profound insight is that rooting is the most efficient way to handle symmetry in planar embeddings. It turns a geometric problem into an algebraic one.
- The Core and Extension Principle: Tutte shows that complex maps can be viewed as "extensions" of simpler "cores." A general map can be decomposed into a non-separable core, and a non-separable map can be decomposed into a 3-connected core (which he calls a c-net).
- Duality as a Counting Tool: By using the concept of a dual map (where faces become vertices and vice versa), Tutte relates the counting of "bicubic" maps (where every vertex has degree 3 and the graph is bipartite) to the counting of general maps.
- Asymptotic Growth: Beyond exact formulas, Tutte uses Stirling’s approximation to show how the number of maps grows as the number of edges $n$ goes to infinity, revealing that the number of maps grows exponentially (roughly by a factor of $12^n$ for general maps).
Key Results
Tutte provides several landmark formulas that are still taught in combinatorics today:
- General Rooted Maps: The number of rooted maps with $n$ edges is given by the surprisingly simple formula: $$a_n = \frac{2(2n)! 3^n}{n! (n+2)!}$$ For $n=1$, there are 2 maps (see Figure 2); for $n=2$, there are 9 (see Figure 3).
- Non-separable Maps: He derives a recursive formula and provides a table of values (e.g., 408 maps for $n=7$ edges).
- 3-Connected Maps (c-nets): He provides an asymptotic estimate for the number of c-nets, showing they grow as $n^{-5/2} 4^n$. He also links these to the theory of "simple perfect rectangles," which are dissections of squares into smaller, unequal squares.
Limitations and Future Work
- Unrooted Maps: While rooting makes the math work, the paper only briefly touches on "unrooted" maps. Counting unrooted maps requires dealing with the symmetries Tutte worked so hard to avoid, which is significantly more difficult.
- Asymmetry Assumption: Tutte notes a "plausible, but unproved" assumption that almost all large c-nets are unsymmetrical. While this intuition is likely correct, it remained a formal gap at the time of writing.
- Higher Genus: This census is strictly for planar maps (genus 0). Counting maps on surfaces like a torus (genus 1) or higher would require even more complex topological machinery.
Summary updated