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 $\Gamma$ be a graph. If $T \subset \Gamma$ is a maximal subtree, then $\Gamma/T$ is a bouquet of $\kappa$ circles and $\pi_1(\Gamma) \simeq \pi_1( \Gamma /T)$. The universal covering of $\Gamma /T$ is a regular tree of degree $\kappa$, so it is also the usual Cayley graph of the free group $F$ of rank $\kappa$. Because a group acts freely on its Cayley graph, we deduce that $\pi_1(\Gamma) \simeq F$.

Conversely, let $F$ be a free group of rank $\kappa$. With the same argument, $F$ is the fundamental group of a bouquet of $\kappa$ circles. $\square$

Notice that in the first part of the proof, $\kappa$ is the cardinal of edges of $\Gamma$ not in $T$. In particular, the fundamental group of a finite graph is a free group of finite rank.

Theorem 1: A subgroup $H$ of a free group $F$ is free. Moreover, if $[F:H], \mathrm{rk}(F) < + \infty$ then

$\mathrm{rk}(H)=1+[F:H] \cdot (\mathrm{rk}(F)-1)$.

Proof. We view $F$ as the fundamental group of a graph $X$. Let $Y \twoheadrightarrow X$ be a covering satisfying $\pi_1(Y) \simeq H$. In particular, the covering induces a structure of graph on $Y$ making the covering cellular; in particular, $H$ is a free group.

If $n=[F:H] < + \infty$, the covering $Y \twoheadrightarrow X$ is $n$-sheeted, hence $\chi(Y)=n \chi(X)$. If $T \subset X$ is a maximal subtree, then $X$ is the disjoint union of $T$ and $\mathrm{rk}(F)$ edges, hence

$\chi(X)= \chi(T)- \mathrm{rk}(F)=1- \mathrm{rk}(F)$;

in the same way, $\chi(Y)= 1- \mathrm{rk}(H)$. Therefore, $\mathrm{rk}(H)=1+n (\mathrm{rk}(F)-1)$. $\square$

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: $\langle a \rangle$ is a finitely-generated subgroup of infinite index in $\mathbb{F}_2 = \langle a,b \mid \ \rangle$. However, the converse turns out to be true for normal subgroups.

Theorem 3: Let $F$ be a free group of finite rank and $H \leq F$ be a non-trivial normal subgroup. Then $H$ is finitely generated if and only if it is a finite-index subgroup.

Proof. Suppose that $H$ is an infinite-index subgroup. Let $X$ be a bouquet of $\mathrm{rk}(F)$ circles so that $F$ be the fundamental group of $X$ and let $Y \twoheadrightarrow X$ be a covering such that $H$ is the fundamental group of the graph $Y$. Noticing that a deck transformation associated to the covering is a graph automorphism of $Y$, we deduce that the group $\mathrm{Aut}(Y)$ of graph automorphisms is vertex-transitive since the covering is normal.

Let $T \subset Y$ be a maximal subtree. Because $H$ is non-trivial, there exists a cycle $C$ in $Y$. Moreover, because $H$ is an infinite-index subgroup the graph $Y$ is infinite and there exist vertices $v_0,v_1, \dots$ of $Y$ satisfying $v_0 \in C$ and $d(v_n,v_m) > \ell g (C)$ for all $n \neq m$; let $\varphi_n \in \mathrm{Aut}(Y)$ be a graph automorphism sending $v_0$ to $v_n$. Then $(\varphi_n(C))$ is a family of disjoint cycles, so there exist infinitely-many edges of $Y$ not in $T$. Therefore, $H$ is not finitely generated. $\square$

Theorem 4: A free group of finite rank $F$ is subgroup separable. In particular, it is residually finite and Hopfian (ie. every epimorphism $F \twoheadrightarrow F$ 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 $F$ be a free group of finite rank and $H \leq F$ be a finitely generated subgroup. Then $H$ is a free factor in a finite-index subgroup of $F$.

Proof. Let $X$ be a bouquet of $n:= \mathrm{rk}(F)$ circles so that $\pi_1(X) \simeq F$ and let $Y \to X$ be a covering so that $\pi_1(Y) \simeq H$. If $T \subset Y$ is a maximal subtree, because $H$ is finitely generated by assumption, there exist only finitely-many edges of $Y$ not in $T$; let $D \subset Y$ be a finite connected graph containing these edges and such that $T \cap D$ is a maximal subtree of $D$. Let $Z$ denote the canonical completion $C(D,X)$.

Now $\pi_1(Z)$ a finite-index subgroup of $\pi_1(X) \simeq F$ and $\{ \text{edges of} \ Z \ \text{not in} \ T \cap D \}$ is a free basis. By construction, this basis contain a free basis of $H$, so $H$ is a free factor in $\pi_1(Z)$. $\square$

Theorem 6: (Howson) Let $S_1$ and $S_2$ be two finitely-genereated subgroups of a free group $F$. Then $S_1 \cap S_2$ 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 $F$ be a free group of finite rank and $n \geq 1$. Clearly, a finite graph has finitely many $n$-sheeted covering (because such a covering is a graph with a fixed number of vertices and edges), so $F$ has finitely many conjugacy classes of groups of index $n$; moreover, a finite-index subgroup’s conjugacy class is necessarily finite (if a subgroup $H$ has index $n$, then $xH=yH$ implies $xHx^{-1}=yHy^{-1}$). Therefore, theorem 7 holds for finitely generated free groups.

Let $G$ be a finitely generated group. Then $G$ is the quotient of a free group, that is there exists an epimorphism $\varphi : G \twoheadrightarrow F$ onto a free group of finite rank. Then, for all $n\geq 1$, $H \mapsto \varphi^{-1}(H)$ defines an injective map from to set of $n$-index subgroup of $G$ into the set of $n$-index subgroup of $F$. The theorem 7 follows. $\square$