¿Cuántos gráficos diferentes de 2 regulares hay con 5 vértices?

Question

Cuántos diferentes 2-regular (simple) de los gráficos hay con 5 vértices?

Solo he pedido una muy similar pregunta, y yo en realidad ya sabe la respuesta a esta pregunta.

Creo que hay muy distintas formas de mirar a esa pregunta (pero tal vez estoy equivocado) y mi cabeza siempre se sienten insatisfechos, incluso si tengo la respuesta. Espero que mi cabeza un poco más satisfecho por el hecho de la comprensión de las diferentes maneras de resolver este problema. Veo este problema ahora como:

---

Sólo por ensayo y error, entiendo que la gráfica debe verse así:

\begin{array}{ccccc} & & 1 & & \\ & ╱ & & ╲ \\ 5 & & & & 2 & \\ | & & & & | \\ 4 & & - & &3 \end{array}

Y como no se $4!$ ciclos de la forma $(12345)\in S_5$, no debe ser $4!/2$ gráficos de esta forma como $(12345)$ $(54321)$ son diferentes ciclos, pero representan el mismo gráfico.

---

Así que esta es una manera de ver este problema, pero estoy interesado en otras formas de pensar de esta pregunta.

Answer 1

En primer lugar vamos a observar que cualquier simple gráfico de $G$ $5$ vértices y $2$-regular debe estar conectado.

En efecto, suponiendo que $G$ está desconectado, uno de los componentes debe tener 2 o menos vértices. Pero entonces ningún vértice en este componente puede tener grado mayor que $2-1=1$.

A continuación, $G$ debe tener un ciclo, ya que no puede ser un árbol. Este ciclo debe tener la longitud de 3, 4 o 5. Pero este ciclo no puede ser conectado a cualquier otro vértice, como los vértices del ciclo ya tienen un grado $2$. Así, el ciclo es un componente de $G$, y desde $G$ está conectado, significa que el ciclo es $G$.

Por lo tanto $G$ es un ciclo de la gráfica, por lo tanto $G$$C_5$.

Como etiqueta gráfico de $C_5$ es el único gráfico. Si usted mira la etiqueta de gráficos, es necesario etiquetar $C_5$ en todas las formas posibles, y su recuento es correcto: si corrige el vértice $\{1\}$ hay $4!$ formas de etiqueta de los otros vértices y de llegar a cada gráfico de dos veces (en sentido horario y antihorario).

P. S. El argumento que he utilizado en el tercer párrafo obras más general: Si $G$ está conectado y $2$-regular, a continuación, $G$ algunos $C_n$.

P. P. S. Si $G$ $2$- regular, pero no necesariamente conectado, a continuación, cada componente es $2$ regular y conectado así que algo de $C_k$. Esto, junto con la observación de que $C_k$ debe tener al menos 3 vértices puede ser utilizado para clasify simple $2$ regular gráficos con $n$ vértices, por pequeño $n$.

Answer 2

Existe, de hecho, sólo uno de los $5$-vértice $2$-gráfico regular, que es isomorfo a la $5$ciclo de:

Este gráfico tiene el diedro grupo (que voy a denotar $D_5$ hoy en día), como su automorphism grupo.

Deje $A$ el conjunto de etiquetado grafos isomorfos a la $5$-ciclo. El grupo simétrico $S_5$ actúa en $A$ por permuting el vértice etiquetas. Sólo hay una órbita en virtud de este grupo de acción, y esta órbita es $A$. Los elementos de $S_5$ que estabilizar una gráfica rotulada en $A$ son precisamente los elementos de $D_5$. Por lo tanto, por la Órbita-Estabilizador Teorema $$|A|=\frac{|S_5|}{|D_5|}=\frac{5!}{10}.$$

En general, el mismo argumento puede ser utilizado para mostrar que el número de marcado gráficos isomorfo al grafo $G$ es $$\frac{|V(G)|!}{|\mathrm{Aut}(G)|}$$ where $V(G)$ is the set of vertices of $G$ and $\mathrm{Aut}(G)$ is the automorphism group of $G$.