# Proving that a group acting freely on a tree is a free group

I want to prove that a group that acts freely on a tree is a free group. The proof I saw used weird things (in particular it considered edges as line segments, and used "half-edges") and I didn't like it so i tried to come up with my own proof, and the one I found seems much simpler, and therefore it seems suspicious (why go with a weird complicated proof when there is a simple, natural one ?). Here goes : I first prove the result assuming the action is transitive : let $G$ be a group acting freely and transitively on the (nonempty) tree $T= (V,E)$. Let $v$ be any vertex in $V$ and for $x$ a vertex, we let $N(x)$ be the set of neighbours of $x$.

I also let $N := N(v)$ for simplicity. For all $n\in N$, there is $g\in G$ with $g\cdot v = n$, because the action is transitive and since the action is free, this $g$ is unique : we denote it by $g_n$.

Then we put $S= \{g_n\mid n\in N\}$ and $S'\subset S$ such that for all $n\in N$, either $g_n$ or $g_n^{-1}$ belongs to $S'$, these options being mutually exclusive.

I want to show that $S'$ is a free generating set for $G$. First of all, it is a generating set : let $g\in G$ and let $x_0 = v, x_1,..., x_m, x_{m+1} = g\cdot v$ be a path from $v$ to $g\cdot v$ in $T$. Since the action is transitive, we can find $g_i$ with $g_i \cdot v = x_i$. Since $\{x_i, x_{i+1}\}\in E$, it follows that $g_{i+1}^{-1}g_i\in S$ and thus, since $g_1\in S$, we get that $g\in \langle S\rangle = \langle S'\rangle$, which is what I wanted to prove.

I now have to prove that $S'$ is a free generating set. But to any reduced word on $S'\cup S'^{-1}$ one can associate a path, and if, when computing the word in $G$ one gets $e$ (the unit of $G$), then we have a cycle in $T$, which is a contradiction with the fact that $T$ is a tree. Therefore $G$ has a free generating set : $G$ is a free group.

Now if the action of $G$ isn't transitive, we make it transitive : let $G$ act freely on the tree $T=(V,E)$. Let $v$ be any vertex in $V$ and $V' := G\cdot v$ (the orbit of $v$). $g\cdot v$ and $h\cdot v$ are connected in an edge in $T' = (V', E')$ if and only if either they are connected in an edge in $T$, of if all paths from one to the other in $T$ don't intersect $G\cdot v$.

Then $T'$ has no cycle because $T$ is a subdivision of $T'$, and $T$ has no cycles. Moreover, by construction, $T'$ is connected : $T'$ is a tree. The obvious action of $G$ on $T'$ is then free and transitive so we can use the previois result : $G$ acts freely and transitively on a tree, so it is a free group.

In conclusion, if $G$ acts freely on a tree, it is free.

My doubts about this proof are about the point where I prove that $S'$ is a free generating set.

They come from this fact : it seems that $\Bbb{Z}/2\Bbb{Z}$ acts freely on the tree with two vertices. The action is obvious, and $1$ has no fixed point, so the action is indeed free. But $\Bbb{Z}/2\Bbb{Z}$ is not a free group. And when looking at how my "proof" goes wheb $G=\Bbb{Z}/2\Bbb{Z}$ and $T$ is the tree with two vertices, the point where it stops working is precisely the point where I claim that $S'$ is a free generating set. While writing this, I see that my mistake is when I claim that I can define $S'$ : for $\Bbb{Z}/2\Bbb{Z}$, since $1= -1$, I cannot define $S'$ as I say. But I know that the theorem is true : what am I not seeing ?

EDIT: I'm adding this because according to another post on math.SE, it seems that the theorem that I'm mentioning (or at least one of its consequences: the Nielsen-Schreier theorem, which states that a subgroup of a free group is itself free) implies the axiom of choice for finite sets. However, in my "proof" I seem to only be using $AC(2)$, i.e. the axiom of choice for sets with $2$ elements (when picking $S'$), but if I remember correctly, the axiom of choice for finite sets isn't a consequence of $AC(2)$, and so I can't have proven the NS-theorem with only $AC(2)$. Can anyone help me spot either the mistake in the proof or the point where I use more than $AC(2)$ ?

• Your proof is fine (it's essentially what I teach my graduate student, and what I'm putting in my $\text{Out}(F_n)$ book). The action of $\mathbb{Z}/2\mathbb{Z}$ on the tree with two vertices and one edge is not a free action: the nontrivial group element has a fixed point in the interior of the unique edge. – Lee Mosher May 27 '17 at 16:15
• Yes, that's correct, the edges (as unordered pairs) cannot be fixed either. That's part of what "free" means for an action on a tree. – Lee Mosher May 27 '17 at 17:07
• By the way, "simple and natural" are in the eyes of the beholder :-) To me, the simplest, most natural way to think of a tree is using topology, where an edge is indeed homeomorphic to $[0,1]$, and its interior is homeomorphic to $(0,1)$ (that is the context of my first comment). For instance, this viewpoint helped me to resolve your $\mathbb{Z}/2\mathbb{Z}$ issue. – Lee Mosher May 27 '17 at 17:10
• There's a very short proof using a bit more topology: the quotient of a free action on a tree is a graph, and the fundamental group of a graph is a free group. – Qiaochu Yuan May 27 '17 at 18:45
• @Max A graph is a topological space - when you visualize one in your head, you're embedding it as a topological subspace of $\Bbb R^3$ for example. – arctic tern May 27 '17 at 21:30

## 1 Answer

It seems that there is an issue with the "treeness" of $T'$ in your original argument. For example, if you consider $F_2=\langle a,b\rangle$ acting on its Cayley graph (which is an infinite regular tree of valency 4), then the subgroup $H$ consisting of all elements of $F_2$ of even length will correspond to orbits that have "every other vertex" along every path. In this case in your definition of $T'$ elements $e$, $ab$, and $ab^{-1}$ will form a triangle as the geodesics between any two of these elements will only pass through $a$, which is not in the orbit.

• Thank you for answering ! The Cayley graph of $G$ can't be a tree because $G$ is not free. As $T'$ is a subdivision of $T$, it can't have cycles, can it ? – Max Apr 13 '18 at 16:36
• Sorry - you are right, of course that my example is not the best here. But I do not see why in the argument $T'$ is a subdivision of $T$. Let me modify my example. Take $F_2$ - a free group of rank 2 and again consider the subgroup of index 2 consisting of all words of even length. Then there will be many copies of the complete graph $K_4$ in $T'$ by the same reason as in my previous example. – Dima Savchuk Apr 14 '18 at 17:04
• Mhm sorry I meant that $T$ is a subdivision of $T'$; and it's because each edge in $T'$ corresponds to an edge in $T$ or a path in $T$ – Max Apr 14 '18 at 17:42
• I meant that I did not see why $T$ was a subdivision of $T'$. Let me be more specific, and then you may be able to clarify my confusion. Take $F_2$ generated by $a$ and $b$ and subgroup $H$ as described above. Then the orbit of the identity will consist of all elements of $H$. My claim is this: points $e$, $ab$ and $ac$ form a triangle in $T'$. Indeed, according to your definition the only path in $T$ that goes from $e$ to $ab$ does not pass through points in $H$, so we connect $e$ and $ab$ by an edge in $T'$. But the same is true for $e$ and $ac$, and $ab$ and $ac$. So $T'$ is not a tree. – Dima Savchuk Apr 15 '18 at 3:18
• Wait, I said "connect them if all paths in $T$ from one to the other don't intersect $G\cdot v$ [Here $H$]"; but here there actually is a path from $ab$ to $ac$ that intersects $H$ : go to $e$, then to $ab$, so you don't connect $ab$ and $ac$: there's no edge there so no triangle – Max Apr 15 '18 at 9:39