5
$\begingroup$

If $T$ is a tree, and $T$ has an odd number of vertices, then $\forall f$, where $f$ is automorphism $\Rightarrow \exists$ fixed point (vertex). What it means:

Formally, an automorphism of a tree $T$ is a permutation $\sigma$ of the vertex set $V$ of tree, such that the pair of vertices $(u, v)$ form an edge if and only if the pair $(\sigma(u),\sigma(v))$ also form an edge.

If $T$ is a tree with vertices ($v1,..vn$), then after applying $f$, some vertex will be always stay in place.

if somebody want to illustrate this, I will do.

  • 0
    "if somebody want to illustrate this, I will do." if you don't understand the problem above, I can illustrate this for more understanding.2012-10-07

1 Answers 1

7

Call the original tree $T_0$. Remove all the leaves of $T_0$ to get a tree $T_1$. Then remove all the leaves of $T_1$ to get $T_2$. After finitely many iterations, you get a tree $T_n$ which is all leaves, and therefore consists of either a single vertex, or two vertices connected by an edge.

Any automorphism $\sigma$ of the original tree $T_0$ must take every $T_i$ to itself. If $T_n$ consists of a single vertex, we are done. If $T_n$ consists of 2 vertices, and $\sigma$ fixes them, we are done. Suppose $\sigma$ reverses the two vertices of $T_n$. Then $\sigma$ fixes the edge $e$ of $T_n$. Remove the edge $e$ from the original tree $T_0$. We get a forest with 2 components, and $\sigma$ must be an automorphism of this forest which reverses the 2 components. But this is impossible, because $T_0$ has an odd number of vertices and therefore the number of vertices in the two components must be different (one must be odd and the other must be even).

  • 0
    Yep, I thought the same. But scared a little bit. Thank you.2012-10-09