Ejercicios resueltos de coloración y planaridad

Estructura: Dos conjuntos disjuntos $U = \{u_1, u_2, u_3\}$ y $V = \{v_1, v_2, v_3, v_4\}$

Cada vértice de $U$ conecta con todos los de $V$.

Número cromático teórico: Todo grafo bipartito tiene $\chi(G) = 2$

Coloración óptima:

• Color 1: $\{u_1, u_2, u_3\}$
• Color 2: $\{v_1, v_2, v_3, v_4\}$

Orden por grado decreciente: Todos los vértices tienen grado 3 o 4

Orden elegido: $v_1, v_2, v_3, v_4, u_1, u_2, u_3$

Resultado codicioso: 2 colores $\checkmark$ (igual al óptimo)

Estructura: Grafo regular de grado 3 con 10 vértices

• Vértices exteriores: $\{0, 1, 2, 3, 4\}$ formando un pentágono
• Vértices interiores: $\{5, 6, 7, 8, 9\}$ formando una estrella pentagonal
• Conexiones: cada exterior $i$ conecta con el interior $i+5$; los interiores forman la estrella $5-7-9-6-8-5$

Propiedad importante: El grafo de Petersen no es bipartito (contiene ciclos impares)

Cotas para el número cromático:

• Cota inferior: $\chi(G) \geq 3$ (contiene triángulos? No, pero ciclos impares sí)
• Cota superior: $\chi(G) \leq \Delta = 3$ (teorema de Brooks: el grafo es conexo y no es completo ni un ciclo impar)

Orden por grado: Todos tienen grado 3, usar orden lexicográfico: 0,1,2,3,4,5,6,7,8,9

Resultado codicioso: 3 colores

Demostración que $\chi(G) = 3$

El grafo de Petersen no contiene triángulos, pero sí contiene ciclos impares (por ejemplo, ciclos de longitud 5).

Coloración óptima encontrada:

• Color 1: {0, 2, 6}
• Color 2: {1, 3, 5, 9}
• Color 3: {4, 7, 8}

Verificación: Comprobar que no hay aristas entre vértices del mismo color.

Para $K_{3{,}4}$ Perfecto debido a la estructura bipartita simple

Para Petersen: Perfecto por casualidad; el orden de los vértices fue favorable

Nota: El algoritmo codicioso no siempre encuentra la coloración óptima. Su calidad depende del orden de procesamiento de los vértices.

Estructura:

• Vértices (V): 8 (las esquinas del cubo)
• Aristas (E): 12 (las aristas del cubo)
• Grado de cada vértice: 3 (cada esquina conecta con 3 aristas)

Verificar consistencia: $\sum \deg(v) = 8 \times 3 = 24 = 2E = 2 \times 12$ $\checkmark$

Fórmula de Euler: $V - E + F = 2$

$8 - 12 + F = 2$

$F = 6$

Interpretación geométrica: El cubo tiene 6 caras, que coincide con el resultado matemático.

El grafo del cubo es plano. Una incrustación planar:

1. Dibujar un cuadrado exterior (4 vértices, 4 aristas)
2. Dibujar un cuadrado interior (4 vértices, 4 aristas)
3. Conectar cada vértice exterior con el interior correspondiente (4 aristas)

Caras en la incrustación planar:

• 1 cara exterior (infinita)
• 4 caras rectangulares (entre cuadrados exterior e interior)
• 1 cara del cuadrado interior

Total: 6 caras $\checkmark$

Estructura geométrica del dodecaedro:

• Caras geométricas: 12 pentágonos regulares
• Vértices: 20 (cada vértice donde se encuentran 3 pentágonos)
• Aristas: 30 (cada arista compartida por 2 pentágonos)

Para el grafo (esqueleto del dodecaedro):

• V = 20
• E = 30
• Grado de cada vértice: 3

Verificar: $\sum \deg(v) = 20 \times 3 = 60 = 2E = 2 \times 30$ $\checkmark$

$V - E + F = 2$

$20 - 30 + F = 2$

$F = 12$

Interpretación: En una incrustación planar del dodecaedro, habría 12 caras, coincidiendo con las 12 caras pentagonales del sólido original.

Condición necesaria para grafos simples: Si $G$ es plano, entonces $E \leq 3V - 6$

Para el cubo:

$E = 12 \leq 3 \times 8 - 6 = 18$ $\checkmark$

Para el dodecaedro:

$E = 30 \leq 3 \times 20 - 6 = 54$ $\checkmark$

Condición más fuerte para grafos sin triángulos: Si $G$ es plano y no tiene triángulos, entonces $E \leq 2V - 4$

Verificar si hay triángulos:

• Cubo: No tiene triángulos (ciclo mínimo = 4)
• Dodecaedro: No tiene triángulos (ciclo mínimo = 5)

Para el cubo: $E = 12 \leq 2 \times 8 - 4 = 12$ $\checkmark$ (igualdad implica planaridad maximal sin triángulos)

Para el dodecaedro: $E = 30 \leq 2 \times 20 - 4 = 36$ $\checkmark$

Ambos grafos satisfacen:

1. La fórmula de Euler
2. Las condiciones necesarias de planaridad
3. Tienen incrustaciones planares conocidas (como proyecciones de los poliedros)

Conclusión: Tanto el cubo como el dodecaedro son grafos planos, y sus números de caras calculados mediante la fórmula de Euler coinciden con la geometría de los sólidos correspondientes.

Teorema: Todo grafo plano puede ser coloreado con a lo sumo 5 colores.

Estrategia de demostración: Inducción sobre el número de vértices, usando propiedades estructurales de grafos planos.

Lema: Todo grafo plano simple tiene al menos un vértice de grado ≤ 5.

Demostración del lema:

• Por Euler: $V - E + F = 2$
• Cada cara tiene al menos 3 aristas en su frontera
• Cada arista pertenece a exactamente 2 caras
• Por tanto: $3F \leq 2E$, entonces $F \leq \frac{2E}{3}$

Sustituyendo en Euler: $V - E + \frac{2E}{3} \geq 2$

$V - \frac{E}{3} \geq 2$

$E \leq 3V - 6$

Si todos los vértices tuvieran grado ≥ 6:

$\sum \deg(v) = 2E \geq 6V$

$E \geq 3V$

Pero esto contradice $E \leq 3V - 6$. Por tanto, existe al menos un vértice con grado ≤ 5.

Base: Para $n \leq 5$ vértices, es trivial colorear con 5 colores.

Paso inductivo: Supongamos que todo grafo plano con $k < n$ vértices es 5-coloreable.

Sea $G$ un grafo plano con $n$ vértices.

• Por el lema, existe un vértice $v$ con $\deg(v) \leq 5$
• Sea $G' = G - v$ (grafo sin el vértice $v$)
• $G'$ es plano con $n-1$ vértices
• Por hipótesis inductiva, $G'$ es 5-coloreable
• Sea $c: V(G') \to \{1{,}2{,}3{,}4{,}5\}$ una 5-coloración de $G'$

Casos:

1. Si $\deg(v) \leq 4$ Los vecinos de $v$ usan a lo sumo 4 colores, quedando al menos 1 color libre para $v$.
2. Si $\deg(v) = 5$ Los 5 vecinos podrían usar los 5 colores. En este caso, usamos un argumento más sofisticado basado en la estructura planar.

Sean los vecinos de $v$: $v_1, v_2, v_3, v_4, v_5$ en orden cíclico, con colores $1, 2, 3, 4, 5$ respectivamente.

Idea clave: Buscar un intercambio de colores que libere un color para $v$.

Considerar el subgrafo $H_{13}$ inducido por vértices de colores 1 y 3.

• Si $v_1 \textbf{ y } v_3$ no están conectados en $H_{13}$: intercambiar colores 1↔3 en la componente de $v_1$. Ahora $v_1$ tiene color 3, liberando el color 1 para $v$.
• Si $v_1 \textbf{ y } v_3$ están conectados en $H_{13}$: existe un camino 1-3 de $v_1$ a $v_3$.

En el último caso, considerar $H_{24}$ (subgrafo de colores 2 y 4):

Como $G$ es plano, el camino 1-3 separa $v_2$ de $v_4$, por tanto no están conectados en $H_{24}$.

Intercambiar colores 2↔4 en la componente de $v_2$, liberando el color 2 para $v$.

Construir rueda $W_4$

• Centro: $c$
• Ciclo exterior: $v_1, v_2, v_3, v_4$ formando un cuadrado
• Aristas: $(c, v_i)$ para $i = 1{,}2{,}3{,}4$ y $(v_i, v_{i+1 \bmod 4})$

Análisis de $W_4$

• El ciclo $v_1 - v_2 - v_3 - v_4$ se colorea alternadamente: colores 1,2,1,2
• El centro $c$ conecta con todos, necesita un tercer color: color 3
• $\chi(W_4) = 3$ (solo necesita 3 colores)

Construir $W_5$ (rueda con 5 rayos):

• Centro: $c$
• Ciclo exterior: $v_1, v_2, v_3, v_4, v_5$ formando un pentágono
• Aristas: $(c, v_i)$ y ciclo $(v_i, v_{i+1 \bmod 5})$

Análisis de $W_5$

• El ciclo impar $C_5$ necesita 3 colores: $v_1(1), v_2(2), v_3(3), v_4(2), v_5(3)$
• Toda 3-coloración del ciclo impar usa los tres colores (con dos no basta)
• Recolorear: $v_1(1), v_2(2), v_3(3), v_4(1), v_5(2)$
• Centro $c$ no puede usar colores 1, 2, 3: necesita color 4
• $\chi(W_5) = 4$

Planaridad: $W_5$ se dibuja como una rueda (centro con 5 rayos), claramente plano.

4 colores necesarios:

• El ciclo $C_5$ (impar) necesita exactamente 3 colores
• El centro conecta con todos los vértices del ciclo, necesitando un cuarto color
• No se puede reducir a 3 colores

Conclusión: $W_5$ es un grafo plano que requiere exactamente 4 colores, demostrando que el Teorema de los Cuatro Colores es ajustado (tight).

Teorema: Un grafo es planar si y solo si no contiene un subgrafo que sea subdivisión de $K_5$ o $K_{3{,}3}$.

Definiciones:

• Subdivisión: Reemplazar aristas por caminos de longitud ≥ 1
• Subgrafo de Kuratowski: Subdivisión de $K_5$ o $K_{3{,}3}$

Es-Planar-Kuratowski(G):

1. Si |V| ≤ 4: RETURN True
2. Verificar condiciones necesarias:
   • Si |E| > 3|V| - 6: RETURN False
   • Si girth = 3 y |E| > 3|V| - 6: RETURN False
   • Si girth ≥ 4 y |E| > 2|V| - 4: RETURN False
3. Buscar subdivisiones de K$_5$:
   • Enumerar todos los subconjuntos de 5 vértices
   • Verificar si inducen una subdivisión de K$_5$
4. Buscar subdivisiones de K$_{3{,}3}$:
   • Buscar biparticiones con |A| = |B| = 3
   • Verificar conexiones completas entre A y B
5. Si no se encuentran: RETURN True

Parámetros de $K_5$

• $|V| = 5$, $|E| = 10$
• Todos los vértices tienen grado 4

Verificar condición necesaria:

$|E| = 10 > 3|V| - 6 = 3 \times 5 - 6 = 9$

Conclusión inmediata: $K_5$ no es planar.

Verificación directa: $K_5$ es exactamente uno de los grafos prohibidos de Kuratowski.

Parámetros de $K_{3{,}3}$

• $|V| = 6$, $|E| = 9$
• Bipartito con conjuntos $A = \{a_1, a_2, a_3\}$ y $B = \{b_1, b_2, b_3\}$
• No contiene triángulos (girth = 4)

Verificar condición necesaria:

Para grafos sin triángulos: $|E| \leq 2|V| - 4$

$9 > 2 \times 6 - 4 = 8$

Conclusión inmediata: $K_{3{,}3}$ no es planar.

Verificación directa: $K_{3{,}3}$ es exactamente el otro grafo prohibido de Kuratowski.

Grafo original: Petersen tiene 10 vértices, 15 aristas

Modificado: 10 vértices, 14 aristas

Condición necesaria: $14 \leq 3 \times 10 - 6 = 24$ $\checkmark$, pero el grafo no tiene ciclos de longitud 3 ni 4 (cintura 5), y para ese caso la cota es $E \leq \frac{5}{3}(V-2) = 13.3$: como $14 > 13.3$, no es planar.

Búsqueda de subdivisiones de $K_5$

Para encontrar una subdivisión de $K_5$, necesitamos:

• 5 vértices que formen el "esqueleto"
• Caminos disjuntos entre cada par de estos vértices

En el grafo de Petersen modificado, esta búsqueda sería computacionalmente intensiva.

Detectar-Kuratowski-Eficiente(G):

1. Preprocesamiento:
   • Remover vértices de grado ≤ 1 (preserva planaridad)
   • Contraer vértices de grado 2 (preserva planaridad)
2. Para cada subconjunto de 5 vértices {v$_1$,...,v$_5$}:
   • Verificar si existe sistema de caminos disjuntos
   • que conecte cada par (v$_i$, v$_j$)
3. Para cada bipartición potencial {A$_1$,A$_2$,A$_3$} ∪ {B$_1$,B$_2$,B$_3$}:
   • Verificar conexiones completas A↔B
4. Usar algoritmo de flujos para verificar caminos disjuntos

Complejidad del algoritmo de Kuratowski: $O(n^6)$ en el peor caso

• $\binom{n}{5}$ subconjuntos para $K_5$: $O(n^5)$
• Verificar caminos disjuntos: $O(n)$ por subconjunto
• Similar para $K_{3{,}3}$

Algoritmos más eficientes:

• Hopcroft-Tarjan: $O(n)$ usando DFS y estructuras auxiliares
• Boyer-Myrvold: $O(n)$ con implementación simplificada

Conclusión: El criterio de Kuratowski proporciona una caracterización teórica completa de planaridad, aunque algoritmos más modernos son más eficientes para la verificación práctica.