Una duda en la prueba de Frucht del teorema de

Question

Estoy tratando de entender la prueba de Frucht del teorema, que es:

Cada finito grupo es isomorfo a la automorphism grupo de unos gráfico simple.

La prueba (de la cual estoy lectura de este libro) comienza de la siguiente manera: Vamos a $\Gamma=\{g_1,\cdots, g_n\}$ ser un grupo. Considere un grafo dirigido $\hat{G_0}$ $V(\hat{G_0})=\Gamma$ y un borde dirigido entre $g_i$ $g_j$ color $k$ donde $g_ig_j^{-1}=g_k$.

A continuación se va a mostrar que $Aut(\hat{G_0})\approx\Gamma$.

A continuación, un gráfico de $G$ se construye: Siempre $g_i$ ha dirigido en el borde de avance en $g_j$ color $k$, luego de que el borde es reemplazado por un (no dirigida) ruta de acceso de la longitud de la $k+2$. En esta $k+2$-camino hay caminos de longitud $1$ conectado a cada punto interior, excepto para el interior de punto próximo a $g_j$ donde se coloca un camino de longitud $2$.

A continuación, el siguiente se establece:

1. Cada automorphism de $\hat{G_0}$ induce un único automorphism de $G$.

2. Si $\alpha$ es un automorphism de $G$, $\alpha$ es inducida por algunos automorphism de $\hat{G_0}$.

Esto termina la prueba.

Lo que no entiendo es como los dos últimos puntos, presumiblemente, sólo establecer que $Aut(\hat{G_0})$ $Aut(G)$ tienen la misma cardinalidad. No establecer que son isomorfos como de los grupos, que es esencial para la conclusión final de que $Aut(G)\approx \Gamma$.

Actualización: no Hay ninguna prueba de (1) que se proporciona en el libro. En lugar de simplemente dice que la prueba es clara! Asumo que lo que se quiere decir es esto: Para cualquier automorphism $f$$\hat{G_0}$, podemos construir un automorphism de $G$ por primera permuting $V(G_0)$ por $f$, entonces el reordenamiento de las rutas de acceso correctamente (el camino de unirse a $g_i$ $g_j$ es enviar a la ruta de unirse a $f(g_i)$$f(g_j)$. La estructura de los caminos es tal que no hay ninguna permutación posible, dentro de un camino particular.).

Answer 1

Reivindicación 1 es de hecho bastante clara como la permutación $f$ de los vértices de $\hat G_0$ induce la correspondiente permutación de los "especiales" de los vértices de $G$ y si un borde dirigido a $ab$ color $k$ es asignado a un borde dirigido a $f(a)f(b)$ (también de color $k$), a continuación, la inducida por automorphism de $G$ mapas de los demás vértices de la correspondiente $k+2$ camino de $a$ $b$a los vértices correspondientes de las $k+2$ camino de$f(a)$$f(b)$, y, en consecuencia, para el adjunto de longitud 1 rutas de acceso.

La reivindicación 2 se basa en la observación de que $\hat G_0$ puede ser reconstruido a partir de $G$: Vértices de grado $1$ son claramente de los archivos adjuntos a los vértices de las rutas que se utilizan como sustitutos de los colores de los bordes, vértices de grado $2$ significan el comienzo de rutas de acceso y, entonces, reconocemos que los vértices corresponden a los originales de los vértices de $\hat G_0$ (es decir, aquellas con grado de $\ge3$ no tener la hoja del vecino) y entre que tal vertces hay un borde de ehich color en qué dirección. En particular, una automorphism de $G$ permutes el conjunto de vértices con grado de $\ge3$ no tener la hoja del prójimo, es decir, permutes los vértices de $\hat G_0$ y el automorphism también debe mapa de rutas de acceso a las rutas de la misma longitud y con "begin" marcador " en el mismo final, es decir, que obtenga una coincidencia mapa de los bordes de $\hat G_0$.

Esto significa que $\operatorname{Aut}(G)$ puede ser visto como un grupo de permutaciones de $\Gamma$ ("el grupo $\operatorname{Aut}(G)$ actos fielmente en el set $\Gamma$") y por la construcción de esta acción es el mismo que el de $\operatorname{Aut}(\hat G_0)$, por lo tanto $\operatorname{Aut}(G)\cong \operatorname{Aut}(\hat G_0)\cong \Gamma$.

---

Recuerdo dando una construcción explícita de un gráfico de aquí, pero eso era para el caso de un gráfico acíclico dirigido. Usted puede tratar de producir una alternativa a prueba de Frucht del teorema de que, como bien de nuevo por la sustitución de un borde dirigido con un reemplazo gráfico tener trivial automorphism grupo, por ejemplo, una longitud de $4$ ruta con uno de los extremos de "marcado" con un grado de $1$ vértice como en su origen.