Algebraic topology gives a strong link between graphs and free groups. Namely, the fundamental group of a graph is a free group, and conversely, any free group is the fundamental group of a graph. Surprisingly, using the framework of graphs and coverings gives a lot of information about free groups. Our aim here is to exhib some purely algebraic results about free groups and to prove them using graphs.
Our main references are Massey’s book, Algebraic Topology. An Introduction, Hatcher’s book, Algebraic Topology, and Stallings’ article, Topology of finite graphs. We refer to these references for the results of algebraic topology we use below.
Theorem 0: The fundamental group of a graph is free. Conversely, a free group is the fundamental group of a graph.
Proof. Let be a graph. If is a maximal subtree, then is a bouquet of circles and . The universal covering of is a regular tree of degree , so it is also the usual Cayley graph of the free group of rank . Because a group acts freely on its Cayley graph, we deduce that .
Conversely, let be a free group of rank . With the same argument, is the fundamental group of a bouquet of circles.
Notice that in the first part of the proof, is the cardinal of edges of not in . In particular, the fundamental group of a finite graph is a free group of finite rank.
Theorem 1: A subgroup of a free group is free. Moreover, if then
Proof. We view as the fundamental group of a graph . Let be a covering satisfying . In particular, the covering induces a structure of graph on making the covering cellular; in particular, is a free group.
If , the covering is -sheeted, hence . If is a maximal subtree, then is the disjoint union of and edges, hence
in the same way, . Therefore, .
Theorem 2: A non-abelian free group contains a free group of infinite rank.
We already proved theorem 2 using covering spaces in the previous note A free group contains a free group of any rank.
We know from theorem 1 that any finite-index subgroup of a finitely generated free group is finitely generated. Of course, the converse is false in general: is a finitely-generated subgroup of infinite index in . However, the converse turns out to be true for normal subgroups.
Theorem 3: Let be a free group of finite rank and be a non-trivial normal subgroup. Then is finitely generated if and only if it is a finite-index subgroup.
Proof. Suppose that is an infinite-index subgroup. Let be a bouquet of circles so that be the fundamental group of and let be a covering such that is the fundamental group of the graph . Noticing that a deck transformation associated to the covering is a graph automorphism of , we deduce that the group of graph automorphisms is vertex-transitive since the covering is normal.
Let be a maximal subtree. Because is non-trivial, there exists a cycle in . Moreover, because is an infinite-index subgroup the graph is infinite and there exist vertices of satisfying and for all ; let be a graph automorphism sending to . Then is a family of disjoint cycles, so there exist infinitely-many edges of not in . Therefore, is not finitely generated.
Theorem 4: A free group of finite rank is subgroup separable. In particular, it is residually finite and Hopfian (ie. every epimorphism is an isomorphism).
It is precisely the content of the note How Stallings proved finitely-generated free groups are subgroup separable. Using the same ideas, we are able to prove the following result:
Theorem 5: (Hall) Let be a free group of finite rank and be a finitely generated subgroup. Then is a free factor in a finite-index subgroup of .
Proof. Let be a bouquet of circles so that and let be a covering so that . If is a maximal subtree, because is finitely generated by assumption, there exist only finitely-many edges of not in ; let be a finite connected graph containing these edges and such that is a maximal subtree of . Let denote the canonical completion .
Now a finite-index subgroup of and is a free basis. By construction, this basis contain a free basis of , so is a free factor in .
Theorem 6: (Howson) Let and be two finitely-genereated subgroups of a free group . Then is finitely-generated.
It is precisely the content of the note Fiber product of graphs and Howson’s theorem for free groups. We conclude with an application holding not only for free groups of finite rank but for any finitely generated group! The clue is that any group is the quotient of a free group.
Theorem 7: A finitely generated group has finitely many subgroups of a given finite index.
Proof. Let be a free group of finite rank and . Clearly, a finite graph has finitely many -sheeted covering (because such a covering is a graph with a fixed number of vertices and edges), so has finitely many conjugacy classes of groups of index ; moreover, a finite-index subgroup’s conjugacy class is necessarily finite (if a subgroup has index , then implies ). Therefore, theorem 7 holds for finitely generated free groups.
Let be a finitely generated group. Then is the quotient of a free group, that is there exists an epimorphism onto a free group of finite rank. Then, for all , defines an injective map from to set of -index subgroup of into the set of -index subgroup of . The theorem 7 follows.