Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I removed the automorphic-forms tag since that's something totally different. –  Ted Oct 7 '12 at 20:28
    
I don't understand the last sentence. –  joriki Oct 7 '12 at 20:36
    
@joriki what sentence? –  jofisher Oct 7 '12 at 20:41
    
As I said, the last one. –  joriki Oct 7 '12 at 21:01
    
"if somebody want to illustrate this, I will do." if you don't understand the problem above, I can illustrate this for more understanding. –  jofisher Oct 7 '12 at 21:14
add comment

1 Answer

up vote 5 down vote accepted

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).

share|improve this answer
1  
Very handy. Thank you! –  jofisher Oct 7 '12 at 21:47
    
I have a small question. The automorphism transfers vertex to the vertex with the same degree (in common case). But in your case transferred the vertices only at the same level from the bottom. Why, if a vertex from ${T}_{i}$ that can not be transferred to a vertex from ${T}_{j}$..? This is the only question. –  jofisher Oct 9 '12 at 12:57
1  
Are you asking why $\sigma$ must map $T_i$ to itself? Because we know an automorphism must map leaves of $T_0$ to other leaves of $T_0$. Therefore, it must also map the rest of $T_0$ to the rest of $T_0$. But the rest of $T_0$ is $T_1$. Therefore $\sigma$ must map $T_1$ to $T_1$, so $\sigma$ is also an automorphism of $T_1$. Now apply this argument repeatedly to see that $\sigma$ maps every $T_i$ to itself. –  Ted Oct 9 '12 at 16:29
    
Yep, I thought the same. But scared a little bit. Thank you. –  jofisher Oct 9 '12 at 17:31
add comment

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.