Decidir si hay circuito euleriano mirando los grados.
Distinguir ese recorrido de un ciclo hamiltoniano.
Colorear vértices adyacentes de distinto color y ver por qué un ciclo impar pide tres.
Dos recorridos y una pintura
Un circuito euleriano recorre cada arista exactamente una vez y vuelve al inicio. Existe en un grafo conexo si y solo si todos los grados son pares. Un ciclo hamiltoniano recorre cada vértice exactamente una vez y vuelve al inicio: le importan los vértices, no cubrir las aristas.
grado par = 0, 2, 4… · ciclo par = número par de vértices · ciclo impar = número impar · coloración propia = vértices unidos por una arista llevan colores distintos · número cromático = mínimo de colores que lo consiguen
El cuadrado de la izquierda tiene cuatro vértices de grado 2. El circuito A-B-C-D-A usa las cuatro aristas, una vez cada una, y es a la vez hamiltoniano porque también visita cada vértice una vez. Se colorea alternando ámbar y verde: los adyacentes quedan distintos y hacen falta 2 colores.
El triángulo de la derecha tiene grados 2, luego también admite circuito euleriano (y hamiltoniano): la vuelta al triángulo. Pero es un ciclo impar. Si intentas dos colores, el tercer vértice está unido a los otros dos, que ya llevan colores distintos, y no le queda ninguno. Hacen falta 3, como en el dibujo: ámbar, verde y claro.
Ciclo de 4
Triángulo
Grados
2, 2, 2, 2
2, 2, 2
¿Circuito euleriano?
sí
sí
¿Ciclo hamiltoniano?
sí, el mismo
sí, el mismo
Colores mínimos
2
3
Gráfico del ejemplo
La figura no es decoración: los trazos corresponden a los números del ejemplo 1.
Ejemplo resuelto 1 — El cuadrado es euleriano
Comprueba los grados del ciclo de 4 y escribe un circuito euleriano.
Cada vértice del cuadrado incide en dos lados. Grados: 2, 2, 2 y 2, todos pares, y el grafo es conexo.Glosa: grado 2 es par. No hace falta que todos valgan lo mismo, solo que ninguno sea impar.
Un circuito: A-B-C-D-A, siguiendo el trazo ámbar. Usa las 4 aristas y no repite ninguna.Glosa: volver al inicio es lo que lo hace circuito; si paras en otro vértice sería un camino euleriano, que aquí no pedimos.
También es hamiltoniano: A, B, C y D aparecen una sola vez antes de cerrar.Glosa: en un ciclo simple las dos nociones coinciden. No coincidirán cuando haya aristas extra.
Comprueba que no queda ninguna arista fuera del recorrido. Si sobrara un lado, no sería euleriano.Glosa: euleriano habla de aristas; si olvidas una, el circuito no sirve.
Ejemplo resuelto 2 — El triángulo pide tres colores
Intenta colorear el triángulo con dos colores y explica dónde se rompe. Da después una coloración con tres.
Pinta el primer vértice de ámbar y el segundo, que es adyacente, de verde.Glosa: dos unidos no pueden compartir color. El segundo queda forzado si solo hay dos colores.
El tercero está unido al primero y al segundo. Ámbar y verde están prohibidos. Con solo dos colores no hay salida.Glosa: el conflicto es local en ese vértice, pero demuestra que todo el grafo necesita otro color.
Con un tercer color (el claro del gráfico) el tercero se pinta y los tres pares de vecinos quedan distintos.Glosa: tres colores bastan. No hacen falta más, porque solo hay tres vértices.
El número cromático del triángulo es 3. Es el ciclo impar más pequeño; todo ciclo impar necesita 3.Glosa: el ciclo de 4, par, sí se pudo hacer con 2. La paridad cambia la coloración.
Ejemplo resuelto 3 — Cuando euleriano y hamiltoniano se separan
Añade al cuadrado una diagonal. ¿Siguen siendo pares los grados? ¿Sigue habiendo ciclo hamiltoniano?
La diagonal suma 1 al grado de dos vértices opuestos. Esos pasan de 2 a 3, que es impar. Los otros dos siguen en 2.Glosa: una arista nueva cambia dos grados, no uno.
Hay grados impares, luego ya no existe circuito euleriano. No intentes recorrerlo: alguna arista se repetirá o alguna quedará fuera.Glosa: la condición de los grados es necesaria. Si falla, se acabó el circuito euleriano.
Sigue habiendo ciclos hamiltonianos: el borde A-B-C-D-A visita cada vértice una vez. La diagonal no es obligatoria en ese recorrido.Glosa: hamiltoniano puede ignorar aristas; euleriano no.
Conclusión: al añadir la diagonal se pierde el circuito euleriano y se conserva un ciclo hamiltoniano. Son propiedades distintas.Glosa: el cuadrado original las tenía las dos; el nuevo grafo solo conserva una.
Ejercicios
Escribe el razonamiento completo en el editor, no solo la cifra. Si el enunciado pide figura, dibújala en el lienzo de esta misma página.
1. Un grado impar
Un grafo conexo tiene grados 2, 2, 2 y 3. ¿Hay circuito euleriano?
Por qué (abre cuando hayas escrito)
No, porque el vértice de grado 3 tiene grado impar. La condición exige que todos sean pares, no que «la mayoría» lo sean. El paso es revisar la lista completa antes de buscar el recorrido: si hay un impar, puedes dejar de dibujar caminos. Con un solo impar el enunciado además sería imposible por el lema de los grados (la suma sería impar), así que en un grafo real los impares van de dos en dos; con uno o más impares el circuito euleriano ya está descartado.
2. Colores del ciclo de 5
Un ciclo de 5 vértices, sin diagonales. ¿Cuántos colores hacen falta como mínimo?
Por qué (abre cuando hayas escrito)
Es un ciclo impar, como el triángulo pero con cinco vértices. Con dos colores, al alternar, el quinto queda al lado del primero y ambos recibirían el mismo color si cierras el ciclo. Ese choque obliga a un tercer color. Tres bastan: repites una pauta ámbar, verde, ámbar, verde y el quinto en claro, cuidando sus dos vecinos. El paso es no fiarte de que «es un ciclo, como el cuadrado»: el cuadrado es par y con dos colores cierra; el de 5 no.
3. Hamiltoniano que no cubre aristas
En el cuadrado con una diagonal, da un ciclo hamiltoniano y señala una arista que ese ciclo no usa.
Por qué (abre cuando hayas escrito)
El borde A-B-C-D-A es un ciclo hamiltoniano: entra cada vértice una vez y vuelve. La diagonal no forma parte de ese ciclo, luego hay una arista sin recorrer. Por eso el ciclo es hamiltoniano pero el recorrido no es euleriano, cosa que ya sabíamos porque hay grados 3. El paso es separar las dos listas: vértices visitados y aristas usadas. Que la primera esté completa no dice nada de la segunda.
Dibuja en el lienzo
Reproduce a mano el gráfico del ejemplo: ejes o nodos, los datos numéricos y una frase con la conclusión. El botón borra el lienzo sin salir de la lección.
Comprueba
Tres preguntas. Responde mentalmente antes de abrir el porqué.
¿Por qué el cuadrado del gráfico tiene circuito euleriano?
Porque es conexo y los cuatro grados valen 2, que es par. Por qué: esa es la condición. El circuito es el propio borde, y usa cada lado una vez. No depende de los colores, que responden a otra pregunta.
¿Por qué el triángulo no se colorea con dos colores?
Porque es un ciclo impar: el tercer vértice toca a los otros dos. Por qué: esos dos ya necesitan colores distintos, y al tercero no le queda ninguno de los dos. Con tres colores, como en el SVG, sí se puede.
¿Todo circuito euleriano es hamiltoniano?
No. Por qué: el euleriano controla aristas y el hamiltoniano, vértices. En el cuadrado simple coinciden. Si un vértice tuviera grado 4, un circuito euleriano pasaría por ese vértice más de una vez y dejaría de ser un ciclo hamiltoniano, aunque cubriera las aristas.
Reto Profesor
Pinta el circuito
Dibuja en el lienzo el cuadrado, escribe el circuito A-B-C-D-A y coloréalo con dos colores. Al lado, un triángulo con tres colores.