Grafos

10. COLOREADO DE GRAFOS
8.
finales.
Ejemplo 8 Horario de exámenes finales Tenemos que hacer un horario para
realizar siete exámenes finales, Numeramos las asignaturas de 1 a 7. Hay
alumnos matriculados en varias asignaturas a la vez, como se indica en la tabla
siguiente. Tenemos la restricción de que un alumno no puede hacer dos
exámenes el mismo día ¿Cuál es el menor número de días que sedeben usar
para hacer el horario?

1-2
1-3
1-4
1-7

2-3
2-4
2-5
2-7

3-4
3-6
3-7

4-5
4-6

5-6
5-7

6-7

Asignación
televisión.
Ejemplo 9. Asignación de frecuencias de emisión de canales de televisión Seis
estaciones de televisión están situadas en una región en lugares cuya distancia
entre ellos se indica en la tabla adjunta. Dos emisoras no pueden emitir en lamisma frecuencia si están a menos de 150 km de distancia entre sí. ¿Cuántas
frecuencias distintas se necesitan?
1
1
2
3
4
5
6

2
3
4
5
85 175 200 50
125 175 100
100 200
210

6
100
160
250
220
100

Definición. El mínimo número de colores necesario para colorear los vértices de
un grafo G se llama número cromático de G y se escribe χ(G).
NOTA: El grafo completo Kn necesitaexactamente n colores para ser coloreado.

1

10.
Ejemplo 10 Construye el grafo dual del mapa siguiente y encuentra el mínimo
número de colores necesarios para colorear el mapa de manera que dos
regiones con el mismo color no tengan frontera común.

GRAN TEOREMA (El teorema de los cuatro colores)
El número cromático de un grafo plano es menor o igual que 4

Historia. Francis Guthrie,estudiante de Augustus de Morgan, se dió cuenta
de que bastaban 4 colores para colorear un mapa de los condados de Inglaterra.
Aquí nació la conjetura. De Morgan hizo publicidad del problema entre los
matemáticos.
El gran teorema fue demostrado por Kenneth Appel y Wolfgang Haken
(EEUU) en 1976. En su demostración fue necesario usar el ordenador para
examinar 2000 configuraciones diferentes demapas, a los que habían reducido el
problema. Necesitaron 1000 horas de ordenador.
Se han dado varias pruebas incorrectas del teorema de los cuatro colores.
La más famosa la del abogado inglés Alfred Kempe que la publicó en 1879 y fue
aceptada como correcta por los matemáticos hasta que en 1890 Pearcy Heawood
encontró un error en la demostración.

PEQUEÑO TEOREMA (El teorema de los cincocolores)
El número cromático de un grafo plano es menor o igual que 5

Para probar el teorema de los 5 colores necesitamos algunas consecuencias de la
mágica fórmula de Euler: C + V = A + 2 en todo grafo plano conexo contando la
cara exterior.

2

COROLARIO 1. Si G es un grafo plano conexo con V vértices y todas sus
caras son de tipo poligonal con 3 o más aristas, se tiene A ≤ 3V – 6.Demostración. Lamemos grado de una cara al número de aristas que bordea a la
cara. Por hipótesis el grado de cada cara es mayor o igual que 3. Como cada cara
comparte dos aristas se tiene 2A ≥ 3C. Usando la fórmula de Euler
A + 2 = C +V ≤

2
A + V ⇔ A ≤ 3V − 6
3

COROLARIO 2. Si G es un grafo plano conexo y todas sus caras son de
tipo poligonal con 3 o más aristas, G tiene al menos unvértice de grado menor o
igual a 5
Demostración. Por el corolario 1, 2A ≤ 6V – 12. Si todos los vértices tuvieran
grado mayor o igual que 6 se tendría 2A ≥ 6V, que contradice la fórmula anterior.
14.
Ejercicio 14 Utiliza el Corolario 1 para demostrar que el grafo completo K5 no
es plano.

PEQUEÑO TEOREMA (El teorema de los cinco colores)
El número cromático de un grafo plano es menor o igualque 5
Demostración. Procedemos por inducción en el número V de vértices del grafo G.
Si V ≤ 5 el resultado es claro. Siempre se puede suponer que las caras del grafo
son de tipo poligonal con 3 o más aristas. Por el corolario 2 tiene que existir en G
un vértice v de grado menor o igual que 5. Consideremos el grafo G-{v} al que
hemos quitado el vértice v y todas las aristas que llegan a v....