Cada automorphism de un árbol con un número impar de vértices tiene un punto fijo

Question

Si $T$ es un árbol, y $T$ tiene un número impar de vértices, a continuación, $\forall f$ donde $f$ es automorphism $\Rightarrow \exists$ punto fijo (el vértice). Lo que significa:

Formalmente, un automorphism de un árbol de $T$ es una permutación $\sigma$ del conjunto de vértices $V$ de árbol, de tal manera que el par de vértices $(u, v)$ forma una arista si y sólo si el par $(\sigma(u),\sigma(v))$ también forma un borde.

Si $T$ es un árbol con vértices ($v1,..vn$), a continuación, después de aplicar el $f$, algunos vértice será siempre permanecer en el lugar.

si alguien quiere ilustrar esto, que voy a hacer.

Answer 1

Llame a la original árbol de $T_0$. Retire todas las hojas de $T_0$ para obtener un árbol de $T_1$. A continuación, retire todas las hojas de $T_1$ conseguir $T_2$. Después de un número finito de iteraciones, se obtiene un árbol de $T_n$ que es todas las hojas, y por lo tanto se compone de un único vértice, o dos vértices conectados por una arista.

Cualquier automorphism $\sigma$ de la original árbol de $T_0$ deben tomar todas las $T_i$ a sí mismo. Si $T_n$ se compone de un solo vértice, hemos terminado. Si $T_n$ se compone de 2 vértices, y $\sigma$ fija, hemos terminado. Supongamos $\sigma$ invierte los dos vértices de $T_n$. A continuación, $\sigma$ corrige el borde de la $e$$T_n$. Quitar el borde de la $e$ desde el árbol original $T_0$. Llegamos a un bosque con 2 componentes, y $\sigma$ debe ser un automorphism de este bosque que invierte el 2 componentes. Pero esto es imposible, porque $T_0$ tiene un número impar de vértices y por lo tanto el número de vértices en los dos componentes deben ser diferentes (uno debe ser impar y el otro debe ser aún).