¿Cuántos circuitos hamiltonianos hay en un grafo completo con n vértices?

Question

¿Cuántos circuitos hamiltonianos hay en un grafo completo, no dirigido y simple con $n$ ¿Vértices?

La respuesta escrita en mi libro es: $$\frac{\left(n-1\right)!}{2}$$

¿Cuál es la explicación combinatoria a esto?

Mi mejor intento fue intentar contar, para cada tamaño de circuito hamiltoniano (triángulos, cuadriláteros, pentágonos, etc.), cuántos hay de cada uno, y sumarlos. Así que traté de contar para cada cantidad de aristas la cantidad como posibilidades, para completarlo a las formas mencionadas.

Es decir, para n vértices, elijo 2 vértices cualesquiera (eso es una arista) y para cada otro vértice conectando desde cada vértice de mi arista por nuevas aristas, puedo crear un triángulo, que es un círculo hamiltoniano de tamaño 3 y así sucesivamente. Pero hay muchas repeticiones y eso es un lío.

A lo mejor no le he pillado el punto, porque la expresión: $$\frac{\left(n-1\right)!}{2}$$

me parece que no es más que la cantidad de círculos de Euler (cada grado de vértice es 2) que ordeno en un círculo, por lo que $(n-1)!$ son las posibilidades a la orden $n$ diferentes elementos en un círculo y dividir por 2, debido a la reflexión.

¿No es un circuito Hamiltoniano en tal gráfico un $n$ -ciclo, por lo que podría ser triángulo, cuadrilátero, etcétera?

Answer 1

Cualquier disposición del $n$ vértices da lugar a un ciclo hamiltoniano. De hecho, podemos agrupar los $n!$ posibles disposiciones en grupos de $2n$ ya que se puede elegir cualquiera de los $n$ vértices desde los que empezar y cualquiera de las dos direcciones en las que listar los vértices. De ello se deduce que existen precisamente $\frac{n!}{2n}$ ciclos hamiltonianos distintos. El resultado es el siguiente.

Edición posterior: Esbozo de un argumento más formal:

1. Sea $A=\{(v_1,\dots,v_n):v_i\in V(G),v_i\ne v_j\mbox{ for } i\ne j\}$ es el conjunto de todas las disposiciones del $n$ vértices. Demostrar que $|A|=n!$ .

2. Demuestre que cada $(v_1,\dots,v_n)$ da lugar a un ciclo hamiltoniano y todos los ciclos hamiltonianos surgen de esta manera. (Muchos de estos ciclos son duplicados unos de otros).

3. Consideremos una relación sobre $A$ : $(v_1,\dots,v_n)\sim(w_1,\dots,w_n)$ sólo si $(v_1,\dots,v_n)$ y $(w_1,\dots,w_n)$ corresponden al mismo ciclo. Demostrar que se trata de una relación de equivalencia.

4. Obsérvese que cada clase de equivalencia tendrá precisamente $2n$ elementos. (Resuelve el caso $n=5$ a mano)

5. Concluir que existen $n!/2n$ clases de equivalencia. Por lo tanto, concluimos que hay $(n-1)!/2$ Ciclos hamiltonianos.