Grafos Eulerianos y Hamiltonianos

Esta es una de las páginas más “de examen”: la diferencia Euler vs Hamilton.

Regla mental

Eulerianos (aristas)

Camino euleriano: recorre todas las aristas exactamente una vez.
Ciclo euleriano: recorre todas las aristas exactamente una vez y vuelve al inicio.

Sea $G$ conexo.

$G$ tiene ciclo euleriano $\Longleftrightarrow$ todos los vértices tienen grado par.
$G$ tiene camino euleriano abierto $\Longleftrightarrow$ exactamente dos vértices tienen grado impar.

Ejemplo 1 — Decidir si hay camino euleriano

Si los grados son $\{3,3,2,2,2\}$, hay exactamente dos vértices impares.

Conclusión: existe camino euleriano abierto, pero no ciclo euleriano.

A diferencia de Euler, no existe un criterio tan simple necesario y suficiente en general. Se usan condiciones suficientes.

Si $G$ es simple con $n\ge 3$ y grado mínimo $\delta(G)$, entonces:

\[\delta(G)\ge \frac{n}{2}\ \Rightarrow\ \text{$G$ es hamiltoniano.}\]

Si $G$ es simple con $n\ge 3$ y para todo par de vértices no adyacentes $u,v$ se cumple

\[\delta(u)+\delta(v)\ge n,\]

entonces $G$ es hamiltoniano.

Ejemplo 2 — Aplicar Dirac

Si $n=6$ y $\delta(G)=3$, entonces

\[3\ge 6/2=3,\]

así que por Dirac el grafo es hamiltoniano.

Ejercicio. En un grafo conexo, hay 4 vértices de grado impar. ¿Existe camino euleriano?

Solución

Por el teorema de Euler:

Con 4 vértices impares no existe ni ciclo ni camino euleriano que recorra todas las aristas una sola vez.