Grafos hamiltonianos y un teorema de Dirac

Un ciclo que pasa por todos los vértices son llamados ciclos Hamiltonianos. Un grafo que contiene un ciclo de Hamilton se llama grafo Hamiltoniano.

Una trayectoria que pasa por todos los vértices se denomina trayectoria Hamiltoniana.

Si el último enlace de un ciclo Hamiltoniano es borrado conseguiremos una trayectoria Hamiltoniana, sin embargo, un grafo no Hamiltoniano puede tener una trayectoria Hamiltoniana.

Ejemplos:

El n-ciclo $C_n$ con n vértices distintos es Hamiltoniano. Ahora, dado cualquier grafo Hamiltoniano G, el supergrafo G’, obtenido por añadir nuevos enlaces entre vértices no adyacentes también es Hamiltoniano. Por ejemplo $K_n$ es un supergrafo de $C_n$ y por lo tanto $K_n$  es Hamiltoniano.

El siguiente teorema, debido a Dirac, nos da condiciones suficientes para tener un grafo Hamiltoniano.

 

Teorema. (Dirac) Si G es un grafo con n vértices, donde $n\geq 3$ y $d(v)\geq n/2$, para cada vértice $v$ de G, entonces G es Hamiltoniano. 

 

Prueba.

Supongamos que G no es Hamiltoniano. Entonces para algún valor $n\geq 3$ hay un grafo no Hamiltoniano H en el cual $d(v)\geq n/2$ para cada vértice de H. Entonces en cualquier supergrafo  K de H esa desigualdad se mantiene si K tiene el mismo conjunto de vértices que H, pues en ese caso a K se lo obtiene simplemente por añadir enlaces a H. Entonces existe un grafo no Hamiltoniano maximal G con n vértices y que satisface la desigualdad $d(v)\geq n/2$ para cada vértice de G.

 

Obviamente G no es la gráfica completa $K_n$, pues dicha gráfica es Hamiltoniana. Luego, hay en G vértices que no están conectados u, v. Sea G+uv un nuevo supergrafo de G. Dado que G es no Hamiltoniano maximal, entonces G+uv es Hamiltoniano, y uv pertenece al ciclo Hamiltoniano.

Sea $C: u=v_1 v_2 v_3.. v_n=v$, ahora sea $S=\{v_i \in C: uv_{i+1}\in E(G)\}$ y $T=\{v_j \in C: vv_{j}\in E(G)\}$. Observemos que v no pertenece al conjunto T ni al conjunto S.

Sea $|S| , |T|$ y  $| S \cup T |$ las cardinalidades de dichos conjuntos. Entonces $|S \cup T|<n$, y para cada enlace incidente con u, corresponde un vértice $v_i \in S$, así $|S|=d(u)$. Usando un argumento parecido, $|T|=d(v)$.

La siguiente idea es interesante: Supongamos que algún vértice $v_k\in S\cap T$, entonces hay dos enlaces, uno que une a u con $v_{k+1}$  y otro que une a v con $v_k$. Esto implica que el conjunto $C'=v_1, v_{k+1}, v_{k+2}, .., v_n, v_k, v_{k-1}, .., v_1$ es un ciclo Hamiltoniano en G, lo que contradice que G sea no Hamiltoniano. Así $S\cap T$ es vacío.

 

Finalmente $|S\cup T|=|S|+|T|-|S\cap T|$ nos da que $|S|+|T|=|S \cup T|$, tal que $d(u)+d(v)<n$. Esto es una contradicción porque $d(u)\geq n/2$ para todo vértice en G. Y la prueba está terminada.