Todos los vértices deben tener grado par.
Un circuito de Euler en un grafo conexo es un camino cerrado que recorre cada arista del grafo exactamente una vez y regresa al vértice inicial. La condición fundamental para que exista tal circuito es elegante y necesaria: un grafo conexo contiene un circuito de Euler si y solo si cada vértice del grafo tiene un grado par. Este concepto nació del famoso problema de los Siete Puentes de Königsberg, donde Leonhard Euler demostró que no existía ninguna ruta que cruzara los siete puentes exactamente una vez y regresara al inicio, precisamente porque las masas de tierra (vértices) tenían un número impar de puentes (aristas) conectándolas.
Para entenderlo de forma intuitiva, imagina que vas caminando por las aristas de un grafo. Cada vez que entras a un vértice por una arista, tienes que salir de él por una arista distinta para seguir el recorrido sin repetir aristas. Por lo tanto, las aristas que llegan a cualquier vértice deben estar en parejas: una para entrar y otra para salir. Si un vértice tuviera un grado impar, eventualmente entrarías en él y no podrías salir sin repetir una arista (te quedarías atrapado), o empezarías ahí y no podrías regresar para cerrar el ciclo.
Este teorema es una herramienta poderosa en combinatoria y teoría de grafos algorítmica. Te permite determinar al instante si una red compleja se puede recorrer sin tener que construir el camino paso a paso. En matemáticas de competencia (como el AIME o la USAMO), esta condición se aplica seguido en problemas de caminatas en cuadrículas, coberturas de aristas y argumentos de paridad en estructuras de grafos. También es la base del algoritmo de Hierholzer, que construye el circuito uniendo ciclos más pequeños.
Teorema de Euler (Existencia de Circuito) Sea $G = (V, E)$ un grafo finito sin vértices aislados. $G$ contiene un circuito de Euler si y solo si:
Teorema de Euler (Existencia de Camino) Un grafo conexo $G$ contiene un camino de Euler (un recorrido que pasa por cada arista exactamente una vez pero empieza y termina en vértices diferentes) si y solo si exactamente dos vértices tienen grados impares. $$ |{v \in V : \deg(v) \equiv 1 \pmod{2}}| = 2 $$
Lema del Apretón de Manos Este lema se usa seguido junto con problemas de circuitos de Euler para establecer restricciones de paridad: $$ \sum_{v \in V} \deg(v) = 2|E| $$
Teorema: Un grafo conexo $G=(V, E)$ con $|E| \geq 1$ tiene un circuito de Euler si y solo si cada vértice tiene un grado par.
Demostración:
Parte 1: Necesidad ($\Rightarrow$) Supón que $G$ tiene un circuito de Euler $C$. Recorre $C$. Cada vez que el camino pasa por un vértice $v$, usa una arista para entrar a $v$ y una arista distinta para salir de $v$. Así que cada visita aporta exactamente $2$ al grado de $v$. Como los vértices de inicio y fin son el mismo, la salida inicial y la llegada final también forman una pareja. Por lo tanto, el grado de cada vértice es una suma de doses, lo que implica que $\deg(v)$ es par para todo $v \in V$.
Parte 2: Suficiencia ($\Leftarrow$) Supón que $G$ es conexo y cada vértice tiene un grado par. Usa inducción sobre el número de aristas $|E|$.
Caso Base: Si $|E|=0$ (y $G$ es un solo vértice), la condición se cumple de forma trivial.
Paso Inductivo: Supón que la afirmación es cierta para todos los grafos conexos con menos de $k$ aristas donde todos los vértices tienen grados pares. Sea $G$ un grafo así con $k$ aristas.
Como cada vértice tiene un grado par y $G$ es conexo (con $k \ge 1$), cada vértice tiene un grado de al menos 2. Empieza a caminar desde un vértice arbitrario $v_0$, recorriendo aristas que no hayas usado. Como cada vértice al que entras tiene un grado par, cada vez que entras a un vértice $u \neq v_0$, habrás usado un número impar de aristas que llegan a $u$. Como $\deg(u)$ es par, debe quedar al menos una arista sin usar para salir de $u$. El recorrido solo puede detenerse cuando regresas a $v_0$ y has usado todas las aristas incidentes disponibles para esa visita específica. Este recorrido forma un ciclo $C$.
Si $C$ contiene todas las aristas de $G$, ya encontraste un circuito de Euler. Si no, considera el grafo $G' = (V, E \setminus E(C))$ que obtienes al quitar las aristas de $C$.
Por la hipótesis de inducción, como cada $H_i$ tiene menos aristas que $G$ y cumple con la condición de grado par, cada $H_i$ tiene un circuito de Euler $C_i$.
Construye el circuito de Euler para $G$ uniendo estos circuitos: Recorre el ciclo original $C$. Cuando encuentres un vértice $u$ que también sea parte de una componente $H_i$, haz una pausa en tu recorrido de $C$, recorre todo el circuito $C_i$ y luego sigue recorriendo $C$. Como cada arista pertenece a $C$ o a exactamente una $H_i$, este camino combinado recorre cada arista exactamente una vez y regresa al inicio.
$\square$