Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I am currently writing a proof in which I need to use the fact that if a tree has no involutions, its automorphism group is trivial (ie, if a tree has any non-trivial automorphisms, then it has at least one automorphism of order 2). Equivalently, the order of the automorphism group of a tree is either equal to 1 or it is even.

I can prove this fact directly myself, but I assume I'm not the first person to have noticed it - does anyone know where I can find a published proof - I've tried a few graph theory text books, but I'm not really sure where to look in the literature.

share|improve this question
    
I guess you have finite trees in mind? The result is false for infinite trees in general. –  Tom De Medts Apr 27 '11 at 14:03

2 Answers 2

up vote 6 down vote accepted

Look for "Automorphisms of Graphs" by P. J. Cameron (google finds the pdf), and look at the result of Polya on page 8 -- it states that the class of automorphism groups of trees is the smallest class containing the trivial group and closed under the operations of "direct product" and "wreath product with the symmetric group $S_n$ for each $n>1.$" Since symmetric groups have even order, your result follows.

share|improve this answer

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.

share|improve this answer
1  
A possible reference for Lemma 1 is Jean-Pierre Serre's wonderful book "Trees", p.20, Corollary to Proposition 10. –  Tom De Medts Apr 27 '11 at 15:12
    
@darij: Your proof of Lemma 2 looks overly complicated. Here is an easier way to phrase your argument. Let $g$ be an arbitrary automorphism of the tree, and assume that $g$ fixes every vertex at level $n$ but moves some vertex $v$ at level $n+1$. Then the subtrees emanating from $v$ and $vg$ are isomorphic. Hence there is an involution of the tree interchanging the subtrees emanating from $v$ and $vg$, fixing all vertices of level $\leq n$ and also fixing all vertices for which the minimal path to the root does not contain $v$ or $vg$. –  Tom De Medts Apr 27 '11 at 15:22
    
Thanks! And Serre gives a very nice strengthening: If the diameter of the tree is even, it has a vertex which is fixed under every automorphism. If the diameter of the tree is odd, it has an edge which is fixed under every automorphism. –  darij grinberg Apr 27 '11 at 15:24
    
You are right about Lemma 2; editing the post. –  darij grinberg Apr 27 '11 at 15:27
    
Oh, and I should have read the OP. Headdesk. –  darij grinberg Apr 27 '11 at 15:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.