3.5. APLICACIONES DE LOS GRAFOS
93
Por ejemplo, el grafo anterior tiene f = 4 caras, e = 8 lados y v = 6 vértices. Tenemos que
4 = 8 − 6 + 2.
Usando esta fórmula es posible mostrar que el problema del Agua, Luz y Teléfono no
tiene solución pues su grafo no es plano.
3.5.3.
El problema de los cuatro colores
Cuando se colorea un mapa de países (o estados) se evita asignarle el mismo color a
países que tengan frontera común. ¿Cuál es el mínimo número de colores que hace falta? La
respuesta es que son suficientes cuatro colores. Esta pregunta estuvo sin responder desde el
siglo XIX hasta el año 1976, cuando Kenneth Apel y Wolfgang Haken la respondieron (por
cierto, haciendo uso del computador). Para ver qué relación guarda este problema con los
grafos, considere por ejemplo el siguiente mapa
A
D
C
B
F
E
Le asociaremos un grafo a este mapa de la siguiente manera. A cada “país” le asociamos
un vértice y colocamos un arco entre cada dos países que tengan frontera común. De esta
manera obtenemos el siguiente grafo
D
&
&
B
&
&
C
&
&
A
F
E
La pregunta original puede ser enunciada de manera equivalente en términos de grafos:
¿Cuántos colores son necesarios para colorear los vértices de un grafo de tal manera que dos
vértices adyacentes no se les asigne el mismo color? Esta fué la pregunta que respondieron
Apel y Haken.
Ejercicios 3.5
1. Considere los siguientes diagramas. Determine si existe un circuito de Euler.