Graphs, Trees & Free Groups

Collapse a spanning tree, cover it, and every subgroup of a free group turns out free.

The idea

Theorem.

The fundamental group of a connected graph is free. If the graph is finite, with $V$ vertices and $E$ edges, the rank is $E - V + 1$.

A graph here means a $1$-dimensional cell complex: a set of vertices, with edges glued on at their two ends. A maximal tree $T$ in a connected graph $X$ is a contractible subgraph containing every vertex; every connected graph has one, and a tree on $V$ vertices has exactly $V - 1$ edges. The figure shows $T$ collapsed to a point, which fuses all the vertices into one and leaves a wedge of circles, one for each of the $E - (V - 1)$ edges outside $T$. Those circles are the loops the rank counts.

So the fundamental group of a graph carries no relations, and one integer, the number of independent loops, records it completely. The theorem gains its power through covering spaces: a covering space of a graph is again a graph, so every group realized as the fundamental group of a cover of a graph is free as well.

Ways to work on it

• Walkthrough. Maximal trees, the free basis of a graph's fundamental group, and the rank of a covering graph.
• Proof. Nielsen–Schreier: a subgroup is a cover, a cover of a graph is a graph, and graphs have free fundamental groups.
• Practice. Rank of a graph, rank and index of a subgroup of a free group, and rank of a covering graph.
• Hardest. Which ranks occur at finite index, Euler characteristic under covers, and a subgroup of infinite rank.

Not sure where to start? Take the ten-question placement test.