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$. Consider this $n$.
WLOG assume that our tree $T$ has more than two vertices (else, Lemma 1 is trivial). Then, if we remove the vertices $v_0$, $v_1$, ..., $v_{n-1}$ from $T$, we are still left with a tree; denote this tree by $T^{\prime}$. (The only thing we need 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.)
The automorphism $f$ of $T$ restricts to an automorphism $f^{\prime}$ of $T^{\prime}$.
Now, apply Lemma 1 to the tree $T^{\prime}$ with the automorphism $f^{\prime}$ instead of the tree $T$ with the automorphism $f$ (here, we use the fact that $T^{\prime}$ is a tree with less vertices than $T$, so we can apply Lemma 1 to it by our induction assumption). Thus the induction step is done, 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!
EDIT: See the comments below for a short proof of Lemma 2.
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^{-1}\left(f\left(d\right)\right)}$. Hence, $f\left(f^{-1}\left(T_{f\left(d\right)}\right)\right)\subseteq f\left(T_{f^{-1}\left(f\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 obviously be extended to an automorphism of order $2$ of the rooted tree $T$ (just let it act as identity on the $T_{d_j}$ for all $j\in\left\lbrace 1,2,...,k\right\rbrace\setminus\left\lbrace i\right\rbrace$ as well as on $p$), 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_{d_1}$, $T_{d_2}$, ..., $T_{d_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 step 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.
