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)$ ?

Solution 1:

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.