Grafos planos y la fórmula de Euler

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Qué hace que un grafo sea plano

Un grafo es plano cuando puede dibujarse en una hoja de papel plana de modo que ninguna arista cruce a otra. Cada vértice se convierte en un punto, cada arista en una curva que une sus dos extremos, y las curvas solo pueden encontrarse en un vértice que compartan. Un dibujo que cumple estas reglas se llama dibujo plano o inmersión del grafo, y un grafo junto con una inmersión fija es un grafo inmerso en el plano.

La diferencia entre las dos expresiones importa más de lo que parece a primera vista. Plano es una propiedad del grafo: pregunta si existe algún dibujo sin cruces. Inmerso en el plano describe un dibujo concreto. Un grafo puede tener un dibujo plano perfectamente válido y también cien dibujos llenos de cruces, y ninguno de los dibujos malos cuenta en su contra. El grafo completo K4 es el primer ejemplo clásico. Si se dibuja como un cuadrado con sus dos diagonales, las diagonales se cruzan. Mueve un vértice al interior del triángulo que forman los otros tres y todos los cruces desaparecen, así que K4 es plano.

La figura también presenta el ejemplo guía de este artículo, el prisma triangular. Tiene un triángulo exterior A, B, C, un triángulo interior D, E, F y tres radios que unen A con D, B con E y C con F:

V = {A, B, C, D, E, F}                                   6 vértices
E = {AB, BC, CA, DE, EF, FD, AD, BE, CF}                  9 aristas

Tres observaciones prácticas aclaran de qué depende la definición y de qué no. Primera, los lazos y las aristas paralelas nunca afectan a la planaridad: una segunda copia de una arista puede dibujarse como una curva fina justo al lado de la primera, y un lazo como un pequeño rizo junto a su vértice. Un multigrafo es plano exactamente cuando lo es su grafo simple subyacente, y por eso las cotas de conteo que aparecen más adelante en este artículo se enuncian para grafos simples. Segunda, el plano y la esfera son intercambiables. La proyección estereográfica convierte un dibujo sobre una esfera en un dibujo en el plano y viceversa, así que un grafo es plano exactamente cuando puede dibujarse sin cruces sobre la superficie de una pelota. Tercera, nunca hacen falta curvas. Wagner en 1936 y Fáry en 1948 demostraron de forma independiente que todo grafo plano simple tiene un dibujo plano en el que cada arista es un segmento de recta, un resultado que suele llamarse teorema de Fáry.

2. Caras: las regiones que crea un dibujo

Recorta un dibujo plano del papel siguiendo sus aristas y el papel se deshace en trozos. Esos trozos son las caras del dibujo. Exactamente una de ellas no está acotada; se llama la cara exterior, y olvidarse de contarla es el despiste más común de todo este tema. El prisma triangular tiene cinco caras: el triángulo interior D, E, F, tres caras de cuatro lados A, B, E, D, B, C, F, E y C, A, D, F, y la cara exterior, que queda fuera del triángulo A, B, C.

La longitud (o grado) de una cara es el número de aristas que recorres al trazar su borde, con una regla que mantiene exacta la contabilidad: una arista que tiene la misma cara a ambos lados, como una arista de un árbol, se recorre dos veces y se cuenta dos veces. Con esa regla cada arista aporta exactamente dos al total, una por cada uno de sus lados, y las caras cumplen su propio lema del apretón de manos:

suma de las longitudes de las caras = 2e

prisma:  3 + 4 + 4 + 4 + 3  =  18  =  2 × 9
         (triángulo interior, tres cuadriláteros, cara exterior limitada por A, B, C)

Esta identidad es el lema del apretón de manos para vértices de la guía de vértices y aristas con caras en lugar de vértices, y es el motor de todas las cotas de las secciones 4 y 5. Las caras pertenecen a un dibujo y no al grafo, así que un grafo con varios dibujos planos puede tener caras de longitudes distintas en cada uno. Une dos vértices x e y mediante cuatro caminos de longitudes 1, 2, 3 y 4. Si se colocan alrededor de x en ese orden, los caminos consecutivos delimitan caras de longitudes 3, 5, 7 y 5. Intercambia los dos caminos del medio y las longitudes de las caras pasan a ser 4, 5, 6 y 5. Lo que no cambia es el número de caras, cuatro en ambos dibujos, y la sección siguiente demuestra que no es casualidad.

3. La fórmula de Euler

Cuenta los vértices, las aristas y las caras de cualquier dibujo plano conexo y verás que una combinación de los tres nunca cambia.

Fórmula de Euler. Para todo grafo conexo inmerso en el plano con v vértices, e aristas y f caras, v − e + f = 2.

Para el prisma, 6 − 9 + 5 = 2. Para K4 dibujado sin cruces, 4 − 6 + 4 = 2. Para un único vértice, 1 − 0 + 1 = 2, ya que el plano vacío a su alrededor es una cara. La demostración es lo bastante corta para darla completa, y merece la pena leerla porque la misma idea, borrar una arista y observar qué cambia, recorre el resto del tema.

Demostración. Fija el número de vértices y usa inducción sobre el número de aristas. Un grafo conexo con el menor número posible de aristas es un árbol, y un árbol tiene e = v − 1 (una de las caracterizaciones reunidas en árboles en teoría de grafos). Un árbol no contiene ningún ciclo, así que su dibujo no encierra ninguna región y solo hay una cara. Entonces v − (v − 1) + 1 = 2, como se quería demostrar.

Si el grafo conexo no es un árbol, contiene un ciclo. Elige una arista de ese ciclo y bórrala. El grafo sigue siendo conexo, porque el resto del ciclo aún une los dos extremos de la arista borrada. En el dibujo, el ciclo es una curva cerrada y, por el teorema de la curva de Jordan, separa el plano en un interior y un exterior. Por tanto, la arista borrada tenía caras distintas a sus dos lados, una dentro del ciclo y otra fuera, y quitarla funde esas dos caras en una. Así, e baja en uno y f baja en uno, y v − e + f no cambia. Por la hipótesis de inducción, el grafo más pequeño cumple la fórmula, así que el grafo original también.

La fórmula tiene una consecuencia que es fácil pasar por alto. El número de caras, f = e − v + 2, depende solo del grafo y no de cómo se dibuje. Por eso los dos dibujos del grafo de cuatro caminos de la sección 2 tenían ambos cuatro caras: con v = 8 y e = 10, todo dibujo plano de ese grafo tiene 10 − 8 + 2 = 4 caras. Si el grafo no es conexo, todas las piezas comparten la cara exterior y la fórmula pasa a ser v − e + f = 1 + k para un grafo con k componentes.

La fórmula es fácil de comprobar con un ordenador. La función siguiente toma un dibujo rectilíneo sin cruces, dado como coordenadas, y recorre cada cara caminando por las aristas y girando siempre, en cada vértice, hacia la siguiente arista en sentido horario. Cada arista tiene dos lados, y cada lado se recorre exactamente una vez.

from math import atan2

def faces(pos, edges):
    """Recorre las caras de un dibujo rectilíneo sin cruces de un grafo conexo."""
    nbrs = {v: [] for v in pos}
    for u, v in edges:
        nbrs[u].append(v)
        nbrs[v].append(u)
    for v, ws in nbrs.items():               # vecinos en sentido antihorario
        x, y = pos[v]
        ws.sort(key=lambda w: atan2(pos[w][1] - y, pos[w][0] - x))
    seen, found = set(), []
    for u, v in edges:
        for dart in ((u, v), (v, u)):        # cada arista tiene dos lados
            face = []
            while dart not in seen:
                seen.add(dart)
                a, b = dart
                face.append(a)
                ws = nbrs[b]
                dart = (b, ws[ws.index(a) - 1])  # en b, gira hacia la siguiente arista en sentido horario
            if face:
                found.append(face)
    return found

pos = {'A': (0, 4), 'B': (-3.5, -2), 'C': (3.5, -2),
       'D': (0, 1.6), 'E': (-1.4, -0.8), 'F': (1.4, -0.8)}
edges = [('A', 'B'), ('B', 'C'), ('C', 'A'), ('D', 'E'), ('E', 'F'),
         ('F', 'D'), ('A', 'D'), ('B', 'E'), ('C', 'F')]
fs = faces(pos, edges)
v, e, f = len(pos), len(edges), len(fs)
print(v, e, f, v - e + f)
# 6 9 5 2
print(sorted(len(face) for face in fs))
# [3, 3, 4, 4, 4]

Las cinco longitudes de las caras son exactamente las que se contaron en la sección 2, y su suma es 18 = 2e. El mismo procedimiento de recorrido, aplicado a una lista abstracta de órdenes de vecinos en lugar de a coordenadas, es la forma en que las bibliotecas de planaridad almacenan una inmersión: una inmersión de un grafo queda descrita por completo por el orden cíclico de las aristas alrededor de cada vértice, una descripción que se conoce como sistema de rotación.

Los poliedros y el origen de la fórmula

Euler no enunció la fórmula para grafos. La enunció para poliedros, sólidos limitados por caras planas, en una carta a Christian Goldbach en noviembre de 1750, y la publicó en dos artículos en la revista de la Academia de San Petersburgo, en el volumen fechado en 1752 y 1753 que se imprimió en 1758. Dibuja un poliedro convexo en el plano mirando a través de una de sus caras, que pasa a ser la cara exterior, y sus esquinas, aristas y caras se convierten en los vértices, aristas y caras de un grafo inmerso en el plano. Los cinco sólidos platónicos dan la misma respuesta:

La historia tiene dos giros muy conocidos. René Descartes había escrito una relación equivalente, formulada en términos de ángulos, en un manuscrito que hoy está perdido; una copia que Leibniz hizo en París en 1675 o 1676 se redescubrió en el siglo XIX y se publicó en 1859–60. Y el propio argumento de Euler, que cortaba las esquinas del sólido una a una, no era una demostración completa según los criterios modernos. Adrien-Marie Legendre dio la primera demostración completa en 1794, usando las áreas de polígonos dibujados sobre una esfera, y Augustin-Louis Cauchy publicó otra en 1813 que aplana el poliedro en una red en el plano y lo desmonta pieza a pieza, una idea cercana en espíritu al argumento anterior. Imre Lakatos construyó su libro Proofs and Refutations (1976) en torno a los extraños «poliedros» que rompen la fórmula, como un marco de cuadro, cuya superficie tiene un agujero. La historia de la teoría de grafos sitúa este resultado junto a la otra aportación fundacional de Euler, los puentes de Königsberg.

4. ¿Cuántas aristas puede tener un grafo plano?

La fórmula de Euler se convierte en un límite estricto para el número de aristas en cuanto se combina con el lema del apretón de manos para caras. El argumento son las tres líneas más útiles de la teoría de grafos planos.

Teorema. Un grafo plano simple con v ≥ 3 vértices tiene como mucho 3v − 6 aristas. Si además no tiene triángulos, tiene como mucho 2v − 4 aristas.

Demostración. Toma un dibujo plano y supón primero que el grafo es conexo. En un grafo simple con al menos tres vértices, toda cara tiene longitud al menos 3: una cara de longitud 1 necesitaría un lazo y una cara de longitud 2 necesitaría dos aristas paralelas, salvo cuando el grafo entero es una sola arista, caso que v ≥ 3 descarta. Sumando sobre todas las caras, 3f ≤ 2e. La fórmula de Euler da f = 2 − v + e, así que 3(2 − v + e) ≤ 2e, que reordenado queda e ≤ 3v − 6. Si el grafo no tiene triángulos, toda cara tiene longitud al menos 4, así que 4f ≤ 2e y la misma sustitución da e ≤ 2v − 4. A un grafo plano no conexo se le pueden añadir aristas entre sus componentes sin crear ningún cruce, y añadir aristas solo hace más difícil cumplir la desigualdad, así que las cotas también valen para él.

La segunda cota abarca todo grafo bipartito, ya que un grafo bipartito no tiene ciclos impares y, en particular, no tiene triángulos. Las dos cotas son casos particulares de una sola desigualdad. Si el ciclo más corto de un grafo plano conexo, su cintura, tiene longitud g, toda cara tiene longitud al menos g, y las mismas tres líneas dan

e ≤ g(v − 2) / (g − 2)

g = 3   →   e ≤ 3v − 6        (cualquier grafo plano simple, v ≥ 3)
g = 4   →   e ≤ 2v − 4        (sin triángulos, así que todo grafo bipartito plano)
g = 5   →   e ≤ 5(v − 2)/3     (sin ciclos de longitud 3 o 4)

La primera cota se alcanza. Un grafo inmerso en el plano en el que toda cara, incluida la exterior, es un triángulo se llama triangulación, y para una triangulación 3f = 2e se cumple con igualdad, así que e = 3v − 6 exactamente. El octaedro (6 vértices, 12 aristas) y el icosaedro (12 vértices, 30 aristas) son triangulaciones. Añadir cualquier arista a una triangulación la hace no plana, y por eso las triangulaciones también se llaman grafos planos maximales. El prisma no es maximal: tiene 9 aristas frente a un techo de 3 × 6 − 6 = 12, y tres diagonales, una en cada cara cuadrilátera, lo llevarían hasta 12.

Hay dos corolarios que se usan constantemente. El primero es que los grafos planos son dispersos: el número de aristas crece solo linealmente con el número de vértices, así que un grafo plano con un millón de vértices tiene menos de tres millones de aristas, mientras que un grafo general con un millón de vértices puede tener casi 500.000 millones. Por eso los algoritmos sobre grafos planos se miden en función de v únicamente, y por eso las listas de adyacencia, y no las matrices, son el formato de almacenamiento natural, como se explica en representación de grafos. El segundo es el lema del grado cinco:

Todo grafo plano simple tiene un vértice de grado como mucho 5.

La suma de los grados es 2e, y 2e ≤ 6v − 12 cuando v ≥ 3, así que el grado medio es menor que 6 y algún vértice debe tener grado 5 o menos. Los grafos con uno o dos vértices cumplen el lema de forma trivial. El lema es ajustado: todos los vértices del icosaedro tienen grado exactamente 5. Es el motor de los teoremas de coloración de la sección 8.

5. Por qué K₅ y K₃,₃ no son planos

Las cotas de aristas convierten «ningún dibujo sirve», una afirmación sobre infinitos dibujos, en un cálculo de una línea.

El grafo completo K5 tiene v = 5 y e = 10. Un grafo plano con 5 vértices tiene como mucho 3 × 5 − 6 = 9 aristas, así que K5 no es plano.

El grafo bipartito completo K3,3 tiene v = 6 y e = 9. La primera cota permite 12 aristas, así que no dice nada. Pero K3,3 es bipartito y, por tanto, no tiene triángulos, y la segunda cota solo permite 2 × 6 − 4 = 8. Nueve aristas son una de más. Este es el clásico acertijo de los tres servicios, que pide conectar tres casas al agua, el gas y la electricidad sin que se crucen tuberías ni cables. Aparece como «Water, Gas, and Electricity» en el libro de Henry Dudeney Amusements in Mathematics de 1917, y la guía de grafos bipartitos da el mismo argumento desde el punto de vista bipartito.

La comparación con el prisma es la parte instructiva. Los dos grafos tienen seis vértices y nueve aristas, y en ambos todos los vértices tienen grado 3, así que ningún recuento de vértices, aristas o grados puede distinguirlos. Lo que los separa es la forma de sus caras: el prisma puede usar dos triángulos, mientras que K3,3 necesitaría que toda cara tuviera al menos cuatro lados, y no hay sitio suficiente para eso.

Los dos grafos son no planos por muy poco. Cada uno puede dibujarse con exactamente un cruce, como muestra la figura, así que su número de cruces es 1. Borrar cualquier arista de cualquiera de los dos deja un grafo plano. Son, en un sentido preciso, los obstáculos más pequeños para la planaridad, y la sección siguiente explica que son los únicos.

Las cotas de conteo tienen un límite que hay que dejar claro: son condiciones necesarias, no suficientes. Un grafo que las incumple seguro que no es plano; un grafo que las cumple puede, aun así, no ser plano. Toma K3,3 y añade una arista entre dos vértices del mismo lado. El nuevo grafo tiene 6 vértices y 10 aristas y ahora contiene triángulos, así que la única cota aplicable es 3v − 6 = 12, que cumple. Sin embargo, contiene K3,3, así que no puede ser plano. El grafo de Petersen queda en medio. Con 10 vértices y 15 aristas supera tanto 3v − 6 = 24 como 2v − 4 = 16, pero su cintura es 5, y la cota de la cintura solo permite 5 × 8 / 3, unas 13,3, es decir, 13 aristas. Quince aristas son demasiadas, y el grafo de Petersen no es plano.

6. Los teoremas de Kuratowski y de Wagner

Dos operaciones relacionan un grafo con los pequeños obstáculos que contiene. Una subdivisión de un grafo sustituye aristas por caminos, insertando en ellos nuevos vértices de grado 2. Subdividir una arista no cambia si un dibujo tiene cruces, ya que los nuevos vértices simplemente quedan sobre la curva, así que una subdivisión de K5 o de K3,3 es tan no plana como el original. Un grafo plano tampoco puede contener un subgrafo no plano, porque borrar partes de un dibujo plano deja un dibujo plano. En 1930 Kazimierz Kuratowski demostró que estos obstáculos evidentes son los únicos.

Teorema de Kuratowski (1930). Un grafo es plano si y solo si no contiene ningún subgrafo que sea una subdivisión de K5 o de K3,3.

La mitad «solo si» es la dirección fácil que se acaba de describir. La mitad «si» es la profunda: todo grafo que no puede dibujarse en el plano debe contener una de estas dos formas, quizá con sus aristas estiradas en caminos largos. Una segunda operación da una versión más limpia. Contraer una arista funde sus dos extremos en un único vértice adyacente a todos sus antiguos vecinos, y un grafo obtenido de G borrando vértices y aristas y contrayendo aristas es un menor de G. La contracción también conserva la planaridad, ya que puedes encoger una arista de un dibujo plano hasta reducirla a un punto.

Teorema de Wagner (1937). Un grafo es plano si y solo si no tiene ni K5 ni K3,3 como menor.

Los dos teoremas son equivalentes, pero no son intercambiables en los ejemplos, y el grafo de Petersen muestra la diferencia. Contrae los cinco radios que unen su ciclo exterior de longitud 5 con su pentagrama interior y los diez vértices se reducen a cinco, cada uno adyacente a los otros cuatro: el grafo de Petersen tiene K5 como menor. No contiene ninguna subdivisión de K5, sin embargo, porque una subdivisión de K5 necesita cinco vértices de grado 4 y todos los vértices del grafo de Petersen tienen grado 3. El teorema de Kuratowski se sigue cumpliendo, gracias a la otra forma. Borra un vértice cualquiera y los 9 vértices y 12 aristas restantes forman una subdivisión de K3,3: tres de los vértices tienen grado 2 y están sobre caminos, y los otros seis se reparten en dos lados de tres.

La forma de Wagner abrió una historia mucho más amplia. La planaridad es cerrada bajo menores: todo menor de un grafo plano es plano. Neil Robertson y Paul Seymour demostraron, en una serie de artículos publicados entre 1983 y 2004, que toda familia de grafos cerrada bajo menores se caracteriza por una lista finita de menores prohibidos, igual que los grafos planos se caracterizan por la lista K5, K3,3. El teorema garantiza que esa lista existe y es finita, pero no dice cuán larga es ni cómo encontrarla.

7. Comprobar la planaridad

Las cotas de conteo de la sección 4 dan una primera prueba instantánea. No pueden demostrar que un grafo es plano, pero cuando fallan demuestran que no lo es, y comprobarlas no cuesta casi nada. La función siguiente calcula la cintura con una búsqueda en anchura desde cada vértice y aplica la cota de la cintura, que incluye tanto 3v − 6 como 2v − 4 como casos particulares.

from collections import deque

def girth(adj):
    """Longitud del ciclo más corto (inf para un bosque): BFS desde cada vértice."""
    best = float('inf')
    for s in adj:
        dist, parent = {s: 0}, {s: None}
        queue = deque([s])
        while queue:
            u = queue.popleft()
            for w in adj[u]:
                if w not in dist:
                    dist[w], parent[w] = dist[u] + 1, u
                    queue.append(w)
                elif parent[u] != w:         # una arista que no es del árbol cierra un ciclo
                    best = min(best, dist[u] + dist[w] + 1)
    return best

def euler_filter(adj):
    """False: seguro que no es plano. True: solo 'no descartado'. Grafos simples y conexos."""
    n = len(adj)
    m = sum(len(ws) for ws in adj.values()) // 2
    g = girth(adj)
    if g == float('inf'):
        return True                          # los árboles siempre son planos
    return m * (g - 2) <= g * (n - 2)        # g = 3 da 3n - 6, g = 4 da 2n - 4

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, []).append(v)
        adj.setdefault(v, []).append(u)
    return adj

prism = graph(['AB', 'BC', 'CA', 'DE', 'EF', 'FD', 'AD', 'BE', 'CF'])
k5 = graph([(i, j) for i in range(5) for j in range(i + 1, 5)])
k33 = graph([(a, b) for a in 'abc' for b in 'xyz'])
petersen = graph([(i, (i + 1) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)]
                 + [(5 + i, 5 + (i + 2) % 5) for i in range(5)])
k33_plus = graph([(a, b) for a in 'abc' for b in 'xyz'] + [('a', 'b')])
for name, adj in [('prism', prism), ('K5', k5), ('K3,3', k33),
                  ('Petersen', petersen), ('K3,3 + edge', k33_plus)]:
    print(f'{name:12} girth {girth(adj)}  passes: {euler_filter(adj)}')
# prism        girth 3  passes: True
# K5           girth 3  passes: False
# K3,3         girth 4  passes: False
# Petersen     girth 5  passes: False
# K3,3 + edge  girth 3  passes: True

El filtro rechaza K5, K3,3 y el grafo de Petersen, y deja pasar el prisma, lo cual es correcto, y K3,3 con una arista extra, lo cual no lo es. «passes» nunca significa más que «no descartado». Cada búsqueda en anchura tarda un tiempo O(v + e) y el filtro lanza una desde cada vértice, así que cuesta O(v(v + e)); un grafo que no supera la prueba más barata e ≤ 3v − 6 puede rechazarse sin llegar a calcular la cintura.

Una respuesta completa necesita un verdadero algoritmo de planaridad. El teorema de Kuratowski no da uno eficiente directamente, ya que buscar subdivisiones es costoso. Hopcroft y Tarjan publicaron la primera prueba de planaridad en tiempo lineal en 1974, basada en la búsqueda en profundidad, y algoritmos posteriores hicieron la idea más sencilla de implementar: el método de adición de aristas de Boyer y Myrvold, de 2004, y el criterio de planaridad izquierda-derecha de de Fraysseix y Rosenstiehl, en el que se basa la implementación de NetworkX. Una buena implementación devuelve un certificado en ambos casos: una inmersión plana cuando el grafo es plano, y un subgrafo de Kuratowski cuando no lo es.

import networkx as nx

def count_faces(embedding):
    seen, f = set(), 0
    for u, v in embedding.edges():           # cada semiarista está en exactamente una cara
        if (u, v) not in seen:
            embedding.traverse_face(u, v, mark_half_edges=seen)
            f += 1
    return f

tests = [('prism', nx.circular_ladder_graph(3)), ('K5', nx.complete_graph(5)),
         ('K3,3', nx.complete_bipartite_graph(3, 3)), ('Petersen', nx.petersen_graph()),
         ('K3,3 + edge', nx.complete_bipartite_graph(3, 3))]
tests[-1][1].add_edge(0, 1)
for name, G in tests:
    planar, cert = nx.check_planarity(G, counterexample=True)
    if planar:
        print(f'{name:12} planar, {count_faces(cert)} faces')
    else:
        branch = sum(1 for _, d in cert.degree() if d > 2)
        kind = 'K5' if branch == 5 else 'K3,3'
        print(f'{name:12} not planar: a subdivision of {kind}, '
              f'{cert.number_of_nodes()} vertices, {cert.number_of_edges()} edges')
# prism        planar, 5 faces
# K5           not planar: a subdivision of K5, 5 vertices, 10 edges
# K3,3         not planar: a subdivision of K3,3, 6 vertices, 9 edges
# Petersen     not planar: a subdivision of K3,3, 9 vertices, 12 edges
# K3,3 + edge  not planar: a subdivision of K3,3, 6 vertices, 9 edges

Cada respuesta viene con su demostración. Para el prisma, el certificado es una inmersión, almacenada como sistema de rotación, y al recorrerla salen 5 caras, como exige la fórmula de Euler. Para K5 y K3,3 el certificado es el grafo entero. Para el grafo de Petersen es una subdivisión de K3,3 que usa 9 de los 10 vértices, exactamente la estructura del panel derecho de la figura anterior, y nunca podría ser una subdivisión de K5 porque ningún vértice tiene grado 4. Los subgrafos de Kuratowski no son únicos, así que otra biblioteca u otra versión puede devolver uno distinto; cualquiera de ellos es una demostración válida.

8. Colorear grafos planos y el teorema de los cuatro colores

El teorema más famoso de los grafos planos es de coloración. Una coloración propia asigna a cada vértice un color de modo que los dos extremos de cada arista sean distintos, y el menor número de colores que funciona es el número cromático, que se estudia en la guía de coloración de grafos con todo detalle. Colorear un mapa para que los países vecinos tengan colores distintos es el mismo problema sobre el grafo plano del mapa, con un vértice por país y una arista por cada frontera compartida.

El lema del grado cinco de la sección 4 ya da una cota con una demostración elemental.

Teorema de los seis colores. Todo grafo plano puede colorearse de forma propia con seis colores como mucho.

Quita un vértice de grado como mucho 5, que existe por el lema, y colorea el resto del grafo, que sigue siendo plano, por inducción. Después vuelve a poner el vértice. Tiene como mucho cinco vecinos, así que al menos uno de los seis colores queda libre para él. La demostración es un algoritmo: quita repetidamente un vértice de grado mínimo y después colorea los vértices en el orden inverso al de su eliminación.

def six_colour(adj):
    """Colorea un grafo plano simple con 6 colores como mucho (voraz, el de menor grado al final)."""
    deg = {v: len(ws) for v, ws in adj.items()}
    removed, order = set(), []
    while len(order) < len(adj):
        v = min((u for u in adj if u not in removed), key=deg.get)  # existe uno de grado <= 5
        removed.add(v)
        order.append(v)
        for w in adj[v]:
            if w not in removed:
                deg[w] -= 1
    colour = {}
    for v in reversed(order):                # como mucho 5 vecinos ya están coloreados
        used = {colour[w] for w in adj[v] if w in colour}
        colour[v] = min(c for c in range(6) if c not in used)
    return colour

# El icosaedro: 12 vértices, 30 aristas, todos los vértices de grado exactamente 5.
edges = []
for i in range(5):
    j = (i + 1) % 5
    top, a, b, c, d, bottom = 0, 1 + i, 1 + j, 6 + i, 6 + j, 11
    edges += [(top, a), (a, b), (a, c), (a, d), (c, d), (c, bottom)]
adj = {v: [] for v in range(12)}
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)
colour = six_colour(adj)
print(len(edges), {len(ws) for ws in adj.values()}, max(colour.values()) + 1)
# 30 {5} 4
print(all(colour[u] != colour[v] for u, v in edges))
# True

En el icosaedro, donde todos los vértices tienen grado exactamente 5, el método usa cuatro colores, que es el mínimo, ya que cada vértice y los cinco vecinos que lo rodean ya necesitan cuatro. La heurística de ordenación no siempre lo hace tan bien, pero nunca necesita más de seis.

Llegar a cinco colores requiere una idea más. En 1879 Alfred Kempe publicó una demostración de que cuatro colores siempre bastan, basada en intercambiar los dos colores a lo largo de una cadena de vértices coloreados de forma alterna, lo que hoy se llama una cadena de Kempe. En 1890 Percy Heawood encontró un fallo en el argumento de Kempe y, en el mismo artículo, rescató la técnica de las cadenas para demostrar que cinco colores siempre bastan. La pregunta se remonta a 1852, cuando Francis Guthrie observó que cuatro colores bastaban para un mapa de los condados de Inglaterra y preguntó si eso se cumplía siempre; su hermano Frederick le hizo llegar la pregunta a Augustus De Morgan.

Teorema de los cuatro colores (Appel y Haken, 1976). Todo grafo plano puede colorearse de forma propia con cuatro colores como mucho.

Kenneth Appel y Wolfgang Haken anunciaron la demostración en 1976 y la publicaron en 1977. Reduce el problema a un conjunto finito de configuraciones, 1.482 en la versión publicada, y comprueba cada una por ordenador, con unas 1.200 horas de cálculo. Fue el primer gran teorema cuya demostración no podía comprobarse a mano. Robertson, Sanders, Seymour y Thomas simplificaron la demostración en 1997 y redujeron el conjunto a 633 configuraciones, y en 2005 Georges Gonthier completó una demostración totalmente formal, comprobada línea a línea en el asistente de demostración Coq, que eliminó cualquier duda persistente sobre el trabajo por ordenador.

Cuatro es el número correcto: K4 es plano y necesita cuatro colores, porque sus cuatro vértices son adyacentes dos a dos. En general, tres colores no bastan, y decidir si un grafo plano dado puede colorearse con tres colores es NP-completo, como demostraron Garey, Johnson y Stockmeyer en 1976, incluso cuando todos los vértices tienen grado como mucho 4. En la otra dirección, Grötzsch demostró en 1959 que todo grafo plano sin triángulos es 3-coloreable. Por último, dos colores bastan exactamente para los grafos bipartitos, sean planos o no.

9. Grafos duales

Todo grafo inmerso en el plano G tiene una pareja, su dual G*. Pon un vértice nuevo dentro de cada cara de G. Después, por cada arista de G, dibuja una arista dual que la cruce y que una los vértices duales de las dos caras situadas a sus lados. Si una arista tiene la misma cara a ambos lados, su arista dual es un lazo, y dos caras que comparten varias aristas quedan unidas por aristas duales paralelas, así que el dual es en general un multigrafo.

El prisma tiene cinco caras, así que su dual tiene cinco vértices. El vértice dual del triángulo interior D, E, F está unido a los tres cuadriláteros, el vértice dual de la cara exterior está unido a esos mismos tres, y los tres cuadriláteros están unidos entre sí formando un triángulo. Ese dual es la bipirámide triangular, dos pirámides triangulares pegadas por su base: 5 vértices, 9 aristas y 6 caras triangulares, una cara por cada uno de los 6 vértices del prisma.

La dualidad intercambia los papeles de los vértices y las caras y conserva las aristas: G* tiene f vértices, e aristas y v caras, así que la fórmula de Euler se lee igual para ambos. Para grafos conexos inmersos en el plano, el dual del dual vuelve a ser el grafo original. Los sólidos platónicos se emparejan por dualidad, el cubo con el octaedro y el dodecaedro con el icosaedro, mientras que el tetraedro es su propio dual.

El dual traduce un tipo de estructura en otro:

• La coloración de caras se convierte en coloración de vértices. Colorear las regiones de un mapa para que las vecinas sean distintas es lo mismo que colorear los vértices del grafo dual. Así es como el teorema de los cuatro colores para mapas se convierte en un enunciado sobre grafos planos.
• Los ciclos se convierten en cortes. Las aristas de un ciclo en G corresponden a un conjunto minimal de aristas duales cuya eliminación desconecta G*, porque el ciclo separa las caras de su interior de las de su exterior. En las redes planas, esto convierte un problema de corte mínimo en un problema de ciclo más corto en el dual, una de las razones por las que el flujo máximo es más rápido en grafos planos que en general (véase flujo máximo y corte mínimo).
• Los árboles generadores se emparejan. Si T es un árbol generador de G, los duales de las aristas que no están en T forman un árbol generador de G*. Contar las aristas da (v − 1) + (f − 1) = e, que vuelve a ser la fórmula de Euler, desde una dirección completamente distinta.

Una advertencia acompaña a la definición. El dual se construye a partir de un dibujo, no del grafo, así que un grafo plano con varias inmersiones distintas puede tener varios duales no isomorfos. Whitney demostró en 1932 y 1933 que esto no puede ocurrir en los grafos 3-conexos planos, los que siguen siendo conexos tras borrar dos vértices cualesquiera: su inmersión en la esfera es esencialmente única, y también lo es su dual. El prisma es 3-conexo, y por eso su dual está bien definido. Por el teorema de Steinitz, los grafos planos 3-conexos son además exactamente los grafos de los poliedros convexos, lo que cierra el círculo de vuelta a Euler.

10. Dónde aparecen los grafos planos

La planaridad es una propiedad geométrica, así que aparece dondequiera que una red tenga que disponerse sobre una superficie y dondequiera que una superficie se divida en regiones.

Los circuitos son la aplicación clásica. En una placa de circuito impreso de una sola capa, las pistas de cobre no pueden cruzarse sin provocar un cortocircuito, así que el grafo de conexiones debe ser plano. Cuando no lo es, los diseñadores llevan algunas pistas por una segunda capa y conectan las capas mediante orificios taladrados llamados vías, o hacen pasar una pista por encima de otra con un cable puente. El número mínimo de cruces en cualquier dibujo de un grafo, su número de cruces, mide lo lejos que está un circuito de ser plano, y el número de capas planas necesarias para alojar todas sus aristas es su espesor.

Los mapas son la segunda. Un mapa de países es un grafo inmerso en el plano cuyas caras son los países, y su dual tiene un vértice por país y una arista por frontera compartida. Colorear los países es colorear el dual, y el teorema de los cuatro colores limita a cuatro el número de colores, siempre que cada país sea una única región conexa. Los atlas reales incumplen esa condición: un país dividido en partes separadas, como Estados Unidos con Alaska o Rusia con Kaliningrado, debe tener el mismo color en dos lugares, y los mapas con restricciones de ese tipo pueden necesitar más de cuatro colores.

Las redes de carreteras y los separadores son la tercera. Lipton y Tarjan demostraron en 1979 que todo grafo plano con n vértices puede dividirse en dos partes, ninguna con más de 2n/3 vértices, quitando solo O(√n) vértices. Los separadores pequeños son la base de los algoritmos de divide y vencerás sobre grafos planos, entre ellos cálculos de caminos más cortos más rápidos. Las redes de carreteras no son exactamente planas, por los puentes y los túneles, pero normalmente también pueden cortarse en trozos grandes quitando pocas intersecciones, que es la propiedad en la que se apoyan los planificadores de rutas basados en particiones.

Las mallas son la última. Una malla de triángulos cerrada de una superficie con forma de esfera, sin huecos ni asas, cumple v − e + f = 2, y como cada triángulo tiene tres aristas y cada arista bordea dos triángulos, 3f = 2e. Juntas, estas igualdades obligan a que f = 2v − 4 y e = 3v − 6. Una malla de una superficie así que no cumple estos recuentos tiene en algún sitio un hueco, un triángulo que falta o un vértice duplicado, lo que convierte los recuentos en una comprobación de coherencia barata cuando se importa o se repara una malla.

11. Más allá del plano: cruces y superficies

Un grafo no plano no es el final de la historia. Dos preguntas naturales miden lo lejos que está de ser plano.

La primera es el número de cruces cr(G), el menor número de cruces en cualquier dibujo. Los grafos planos tienen número de cruces 0, y K5 y K3,3 tienen número de cruces 1. Calcularlo es NP-difícil en general, e incluso para los grafos completos solo se conocen valores exactos en casos pequeños.

La segunda es dibujar sobre otra superficie. Un toro, la superficie de un dónut, tiene un agujero, y el agujero da a las aristas una forma de rodearse unas a otras. Tanto K5 como K3,3 pueden dibujarse sin cruces sobre un toro, y también K7. La fórmula de Euler se generaliza: un grafo inmerso en una superficie con g agujeros, de modo que cada cara sea un disco, cumple

v − e + f = 2 − 2g

plano o esfera    g = 0:   v − e + f = 2
toro              g = 1:   v − e + f = 0         K7 en un toro:  7 − 21 + 14 = 0

El número 2 − 2g es la característica de Euler de la superficie, uno de los primeros invariantes de la topología. Heawood la usó en su artículo de 1890 para acotar el número de colores necesarios en una superficie con g agujeros, y la exactitud de la cota para todo g ≥ 1 la demostraron Ringel y Youngs en 1968. Para el toro la respuesta es 7, y K7 muestra que de verdad pueden hacer falta siete colores. El plano, donde la misma fórmula daría 4, fue el único caso que su trabajo no cubría; ese era el teorema de los cuatro colores.

12. Errores comunes

13. Glosario

15. Referencias

Las definiciones, teoremas y atribuciones anteriores proceden de estas fuentes, ordenadas cronológicamente.

1. Euler, L. (1758). "Elementa doctrinae solidorum." Novi Commentarii Academiae Scientiarum Petropolitanae 4 (1752/53), 109 a 140. La fórmula de los poliedros, enunciada sin demostración.
2. Euler, L. (1758). "Demonstratio nonnullarum insignium proprietatum, quibus solida hedris planis inclusa sunt praedita." Novi Commentarii Academiae Scientiarum Petropolitanae 4 (1752/53), 140 a 160. La demostración de Euler cortando esquinas.
3. Legendre, A.-M. (1794). Éléments de géométrie. París. La primera demostración completa, mediante polígonos esféricos.
4. Cauchy, A.-L. (1813). "Recherches sur les polyèdres. Premier mémoire." Journal de l'École Polytechnique 9 (16e cahier), 68 a 86.
5. Kempe, A. B. (1879). "On the Geographical Problem of the Four Colours." American Journal of Mathematics 2(3), 193 a 200.
6. Heawood, P. J. (1890). "Map-Colour Theorem." Quarterly Journal of Pure and Applied Mathematics 24, 332 a 338. El fallo en la demostración de Kempe, el teorema de los cinco colores y la cota para otras superficies.
7. Dudeney, H. E. (1917). Amusements in Mathematics. Londres: Thomas Nelson. Problema 251, "Water, Gas, and Electricity."
8. Steinitz, E. (1922). "Polyeder und Raumeinteilungen." En Encyklopädie der mathematischen Wissenschaften, Band 3 (Geometrie), Teil 3AB12, 1 a 139. Leipzig: Teubner.
9. Kuratowski, K. (1930). "Sur le problème des courbes gauches en topologie." Fundamenta Mathematicae 15, 271 a 283.
10. Whitney, H. (1932). "Non-separable and Planar Graphs." Transactions of the American Mathematical Society 34(2), 339 a 362. Duales combinatorios.
11. Whitney, H. (1933). "2-Isomorphic Graphs." American Journal of Mathematics 55, 245 a 254. Unicidad de la inmersión de los grafos planos 3-conexos.
12. Wagner, K. (1936). "Bemerkungen zum Vierfarbenproblem." Jahresbericht der Deutschen Mathematiker-Vereinigung 46, 26 a 32. Dibujos con líneas rectas.
13. Wagner, K. (1937). "Über eine Eigenschaft der ebenen Komplexe." Mathematische Annalen 114, 570 a 590. La planaridad mediante menores prohibidos.
14. Fáry, I. (1948). "On Straight Line Representation of Planar Graphs." Acta Scientiarum Mathematicarum (Szeged) 11, 229 a 233.
15. Grötzsch, H. (1959). "Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel." Wissenschaftliche Zeitschrift der Martin-Luther-Universität Halle-Wittenberg, Mathematisch-Naturwissenschaftliche Reihe 8, 109 a 120.
16. Ringel, G. y Youngs, J. W. T. (1968). "Solution of the Heawood Map-Coloring Problem." Proceedings of the National Academy of Sciences 60(2), 438 a 445.
17. Hopcroft, J. y Tarjan, R. (1974). "Efficient Planarity Testing." Journal of the ACM 21(4), 549 a 568.
18. Garey, M. R., Johnson, D. S. y Stockmeyer, L. (1976). "Some Simplified NP-Complete Graph Problems." Theoretical Computer Science 1(3), 237 a 267. La 3-colorabilidad de grafos planos es NP-completa.
19. Lakatos, I. (1976). Proofs and Refutations: The Logic of Mathematical Discovery. Edición de J. Worrall y E. Zahar. Cambridge: Cambridge University Press.
20. Appel, K. y Haken, W. (1977). "Every Planar Map is Four Colorable. Part I: Discharging." Illinois Journal of Mathematics 21(3), 429 a 490.
21. Appel, K., Haken, W. y Koch, J. (1977). "Every Planar Map is Four Colorable. Part II: Reducibility." Illinois Journal of Mathematics 21(3), 491 a 567.
22. Lipton, R. J. y Tarjan, R. E. (1979). "A Separator Theorem for Planar Graphs." SIAM Journal on Applied Mathematics 36(2), 177 a 189.
23. Federico, P. J. (1982). Descartes on Polyhedra: A Study of the De Solidorum Elementis. Nueva York: Springer. El manuscrito de Descartes y la copia de Leibniz.
24. de Fraysseix, H. y Rosenstiehl, P. (1985). "A Characterization of Planar Graphs by Trémaux Orders." Combinatorica 5(2), 127 a 135. El criterio izquierda-derecha.
25. Robertson, N., Sanders, D. P., Seymour, P. y Thomas, R. (1997). "The Four-Colour Theorem." Journal of Combinatorial Theory, Series B 70(1), 2 a 44.
26. Boyer, J. M. y Myrvold, W. J. (2004). "On the Cutting Edge: Simplified O(n) Planarity by Edge Addition." Journal of Graph Algorithms and Applications 8(3), 241 a 273.
27. Robertson, N. y Seymour, P. D. (2004). "Graph Minors. XX. Wagner's Conjecture." Journal of Combinatorial Theory, Series B 92(2), 325 a 357.
28. Gonthier, G. (2008). "Formal Proof: The Four-Color Theorem." Notices of the American Mathematical Society 55(11), 1382 a 1393.
29. Bondy, J. A. y Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. Springer. Capítulos 10 y 11, sobre grafos planos y el problema de los cuatro colores.
30. Diestel, R. (2017). Graph Theory, 5.ª edición. Graduate Texts in Mathematics 173. Berlín: Springer. Capítulo 4, sobre grafos planos.