In the following, all trees are finite trees.

First a lemma:

Lemma 1. Let $T$ be a tree, and $f:T\to T$ be an automorphism of this tree. Then, either there exists a vertex of $T$ fixed by $f$, or there exist two vertices of $T$ mutually mapped to each other by $f$.

First proof of Lemma 1. We prove Lemma 1 by strong induction over the number of vertices of $T$. Here is the induction step:

Let $ v_0$ be a vertex of $T$ which has only one neighbour (such a vertex clearly exists). The automorphism $ f$ maps it to a vertex $ v_1$ which also has only one neighbour. This vertex is, in turn, mapped to a new vertex $ v_2$ which also has only one neighbour. And so on, until we find an $ n$ such that $ v_n=v_0$. Now, apply Lemma 1 to the tree $ T\setminus \left\lbrace v_0,v_1,...,v_{n-1}\right\rbrace$ (this is a tree with less vertices, so we can apply Lemma 1 to it by our induction assumption). The only thing one needs to care about is that this tree is nonempty, but if it is empty, then every vertex of $ T$ must have had one neighbour only, meaning that $ T$ is the tree on two vertices. Anyway, the induction step is done in every case, and Lemma 1 is proven.

Second proof of Lemma 1. Consider the tree $ T$ as a topological space $ X$, and extend $ f$ to an automorphism $ g$ of this space $ X$ (by setting $ g\left(v\right) = f\left(v\right)$ for any vertex $ v$ of $ T$, and extending to each edge by linearity). Then, we want to show that this topological automorphism $ g$ has a fixed point (because if such a fixed point is a vertex of the tree, we get a fixed vertex, while if it is an interior point of an edge, we get a fixed edge). By the Lefschetz fixed-point theorem, this will be immediate once we succeed to show that $ \sum_{k\geq 0}\left( - 1\right)^k\mathrm{Tr}\left(g_*\mid H_k\left(X,\mathbb{Q}\right)\right)\neq 0$. This simplifies to $ \mathrm{Tr}\left(g_*\mid H_0\left(X,\mathbb{Q}\right)\right)\neq \mathrm{Tr}\left(g_*\mid H_1\left(X,\mathbb{Q}\right)\right)$ (because the space $ X$ is $ 1$-dimensional). Now, $ \mathrm{Tr}\left(g_*\mid H_1\left(X,\mathbb{Q}\right)\right) = 0$ (since $ H_1\left(X,\mathbb{Q}\right) = 0$, because $ X$ is contractable), but $ \mathrm{Tr}\left(g_*\mid H_0\left(X,\mathbb{Q}\right)\right)\neq 0$ (because $ H_0\left(X,\mathbb{Q}\right)$ is $ \mathbb{Q}$ (since the space $ X$ has one connected component), and $ g_*$ is an automorphism of $ H_0\left(X,\mathbb{Q}\right)$ (because $ g$ is an automorphism of $ X$)), thus $ \mathrm{Tr}\left(g_*\mid H_0\left(X,\mathbb{Q}\right)\right)\neq \mathrm{Tr}\left(g_*\mid H_1\left(X,\mathbb{Q}\right)\right)$, and we are done.

Next, we show:

Lemma 2. Let $T$ be a rooted tree. If $T$ has a nontrivial automorphism, then $T$ has an automorphism of order $2$.

Note that an automorphism of a rooted tree means an automorphism which keeps the root fixed!

Proof of Lemma 2. We prove Lemma 2 by strong induction over the number of vertices of $T$. Here the induction step:

Assume that $T$ has a nontrivial automorphism. Let $f$ be such an automorphism. Then, $f\neq\mathrm{id}$. Let $p$ be the root of $T$. Then, $f\left(p\right)=p$.

Let $d_1$, $d_2$, ..., $d_k$ be the children (= direct descendants) of $p$. For every vertex $d$ of T, let $T_d$ be the subtree of $T$ formed by all descendants of $d$ (which means $d$ itself, its children, the children of its children, etc.). Clearly, every vertex of $T$ except of $p$ is a vertex of one and only one of the subtrees $T_{d_1}$, $T_{d_2}$, ..., $T_{d_k}$.

Now, we see that:

(1) For every vertex $d$ of $T$, we have $f\left(T_d\right)\subseteq T_{f\left(d\right)}$.

This is because the vertices of $T_d$ can be characterized as those vertices of $T$ which have $d$ among their ancestors, and thus their images under $f$ must have $f\left(d\right)$ among their ancestors (because the relation "being an ancestor of" is invariant under any automorphism of a rooted tree).

Here is a stronger result:

(2) For every vertex $d$ of $T$, we have $f\left(T_d\right)= T_{f\left(d\right)}$.

In fact, let us apply the relation (1) to $f^{-1}$ and $f\left(d\right)$ instead of $f$ and $d$. Thus we obtain $f^{-1}\left(T_{f\left(d\right)}\right)\subseteq T_{f\left(f^{-1}\left(d\right)\right)}$. Hence, $f\left(f^{-1}\left(T_{f\left(d\right)}\right)\right)\subseteq f\left(T_{f\left(f^{-1}\left(d\right)\right)}\right)$. Since $f$ is bijective (being an automorphism), this becomes $T_{f\left(d\right)}\subseteq f\left(T_d\right)$. Combined with (1), this yields $f\left(T_d\right)= T_{f\left(d\right)}$, and thus (2) is proven.

For every vertex $d$ of $T$, we regard $T_d$ as a rooted tree with root $d$. Now we distinguish between two cases:

Case 1. There exist two distinct elements $i$ and $j$ of $\left\lbrace 1,2,...,k\right\rbrace$ such that $f\left(d_i\right)=d_j$.

Case 2. Every $i\in\left\lbrace 1,2,...,k\right\rbrace$ satisfies $f\left(d_i\right)=d_i$.

Clearly, these two cases cover all possibilities.

Consider Case 2 first. In this case, every $i\in\left\lbrace 1,2,...,k\right\rbrace$ satisfies $f\left(d_i\right)=d_i$. Thus, (2) yields that every $i\in\left\lbrace 1,2,...,k\right\rbrace$ satisfies $f\left(T_{d_i}\right)=T_{f\left(d_i\right)}=T_{d_i}$. Therefore, the automorphism $f$ of $T$ can be decomposed into automorphisms of the rooted subtrees $T_{d_1}$, $T_{d_2}$, ..., $T_{d_k}$. At least one of these automorphisms is nontrivial (because $f$ is nontrivial). That is, there exists some $i\in\left\lbrace 1,2,...,k\right\rbrace$ such that the rooted tree $T_{d_i}$ has a nontrivial automorphism. For this $i$, we can then conclude that there exists an automorphism of order $2$ of the rooted tree $T_{d_i}$ (by Lemma 2, applied to the smaller tree $T_{d_i}$ instead of $T$, which is legitimate since we are doing a strong induction). This automorphism can thus be extended to an automorphism of order $2$ of the rooted tree $T$, and the induction step is complete in Case 2.

Now let us study Case 1. In this case, there exist two distinct elements $i$ and $j$ of $\left\lbrace 1,2,...,k\right\rbrace$ such that $f\left(d_i\right)=d_j$. Consider these $i$ and $j$. By (2) we have $f\left(T_{d_i}\right)=T_{f\left(d_i\right)}=T_{d_j}$, so that $f$ induces an isomorphism $g:T_{d_i}\to T_{d_j}$ of rooted trees. Now, we can define an endomorphism $h$ of the rooted tree $T$ as follows:

• let $h\left(u\right)=g\left(u\right)$ for every $u\in T_{d_i}$;

• let $h\left(u\right)=g^{-1}\left(u\right)$ for every $u\in T_{d_j}$;

• let $h\left(u\right)=u$ for every $u\in T_{d_r}$ for any $r\in\left\lbrace 1,2,...,k\right\rbrace\setminus\left\lbrace i,j\right\rbrace$;

• let $h\left(p\right)=p$.

This definition is legitimate since the set of the vertices of $T$ is the disjoint union of the sets of the vertices of $T_1$, $T_2$, ..., $T_k$ and the one-element set $\left\lbrace p\right\rbrace$.

Clearly, $h$ is an automorphism of order $2$ of the rooted tree $T$, so we have shown the assertion of Lemma 2 for our $T$, and the induction step is complete in Case 1.

We have thus completed the induction in both cases, and therefore proven Lemma 2.

Theorem 3. Let $T$ be a (non-rooted) tree. If $T$ has a nontrivial automorphism, then $T$ has an automorphism of order $2$.

Proof of Theorem 3. Assume that $T$ has a nontrivial automorphism. Let $f$ be such an automorphism. Then, $f\neq\mathrm{id}$. Lemma 1 yields that either there exists a vertex of $T$ fixed by $f$, or there exist two vertices of $T$ mutually mapped to each other by $f$. But in the latter case, we are done (because if there exist two vertices of $T$ mutually mapped to each other by $f$, then $f$ must have an even order, and thus some power of $f$ has order $2$). So let us consider the former case only. In this case, there exists a vertex of $T$ fixed by $f$. Let $p$ be such a vertex. Then, considering $p$ as a root, we make $T$ into a rooted tree, and $f$ becomes a nontrivial automorphism of this rooted tree. Thus, by Lemma 2, the rooted tree $T$ has an automorphism of order $2$. Theorem 3 is proven.