Emparejamientos, coloraciones y planaridad

En un grafo finito simple no dirigido, un emparejamiento M es un conjunto de aristas sin vértices compartidos. Un vértice está cubierto si pertenece a una de ellas y libre si no. Es perfecto cuando cubre todos: cada arista cubre dos vértices distintos, así un perfecto exige un número par de vértices.

Maximal significa que no podemos añadir otra arista conservando las actuales. Máximo significa que no existe ningún emparejamiento de mayor tamaño. No son sinónimos: mejorar puede requerir quitar aristas y reorganizar, como en la cadena de la figura. En un grafo bipartito, sus dos partes pueden representar personas y tareas compatibles.

Respecto a M, un camino aumentante alterna aristas fuera y dentro del emparejamiento, empezando y terminando en vértices libres. Al invertir las elecciones a lo largo del camino entran una arista más de las que salen. Los vértices internos conservan una arista elegida y los extremos libres pasan a estar cubiertos.

Un emparejamiento es máximo si y solo si no tiene camino aumentante. Para la dirección difícil, compáralo con otro mayor: las aristas que aparecen en uno solo forman componentes de grado como máximo dos, caminos o ciclos alternantes. Los ciclos tienen igual cantidad de cada elección; como el segundo emparejamiento es mayor, algún camino tiene una arista suya de más.

Sus extremos están libres para M y es un camino aumentante.

En un grafo bipartito finito con partes A y B, N(S) reúne todos los vecinos de los vértices de S⊆A. Para cubrir A sin repetir tareas es necesario |N(S)|≥|S| para todo S: esas personas necesitan tareas distintas. Hall afirma que también es suficiente. Si |A|=|B|, cubrir A cubre todo el grafo; si B es mayor, pueden quedar tareas libres.

Veamos la suficiencia usando caminos aumentantes. Tomamos un emparejamiento máximo. Si deja libre a∈A, exploramos desde a por aristas no elegidas hacia B y por elegidas de vuelta a A. Sea S el conjunto de A alcanzado y T el de B. Ningún vértice de T está libre, porque daría un camino aumentante.

Cada vértice de T está emparejado con un vértice distinto de S, y S salvo a se alcanza precisamente por esas parejas. Además N(S)=T: los vecinos no emparejados se exploran y la pareja de cada miembro alcanzado ya pertenece a T.

No puede quedar nadie de A libre.

Una coloración propia asigna colores distintos a los extremos de cada arista. χ(G) es el menor número posible. Exhibir k colores solo prueba χ≤k; demostrar que hacen falta al menos k prueba χ≥k. Para concluir igualdad necesitamos ambas partes.

Una clique de tamaño t, donde cada pareja es adyacente, exige t colores. Por otro lado, si el grado máximo es Δ, un algoritmo voraz dispone siempre de un color entre Δ+1: al llegar a un vértice, sus vecinos anteriores prohíben como máximo Δ. Esto prueba ω(G)≤χ(G)≤Δ+1; no garantiza que el resultado voraz sea óptimo ni que una clique explique toda dificultad.

Un grafo es bipartito si V se divide en dos partes sin aristas dentro de cada una. Esto equivale a una coloración con a lo sumo dos colores. Si tiene alguna arista, χ=2; si es no vacío y no tiene aristas, χ=1. La definición admite partes vacías cuando corresponda.

También equivale a no contener ciclos impares. Un ciclo impar no permite alternar dos colores y cerrar bien. Para la otra dirección se colorea cada componente según paridad de la distancia desde un origen. Una arista entre la misma paridad produciría un recorrido cerrado impar; borrar segmentos repetidos conserva algún recorrido cerrado impar hasta obtener un ciclo impar, contradicción.

Un grafo es planar si admite una representación en el plano donde las aristas solo se encuentran en sus extremos compartidos. Un grafo plano incluye un dibujo concreto sin cruces. Un dibujo con un cruce no prueba que todos los dibujos deban tenerlo.

En un dibujo plano, las caras son las regiones del complemento; la exterior también cuenta. Los segmentos se pueden curvar sin alterar conexiones. Poner un punto en un cruce y tratarlo como vértice modifica el grafo: no es simplemente redibujar el original.

Un árbol tiene m=n−1 y una sola cara, la exterior. Si hay un ciclo, borrar una de sus aristas conserva conexión y fusiona dos caras: m y f bajan uno, y la expresión no cambia. Repitiendo se llega al árbol, lo que demuestra Euler.

Se pueden conectar las componentes mediante c−1 nuevas aristas sin cruces y sin crear caras nuevas; aplicar la fórmula conexa da la versión general. La hipótesis de representación plana ya debe estar justificada: no se usa Euler para declarar planar cualquier grafo por despejar un número.

Para un grafo simple plano conexo con n≥3, cada borde de cara tiene al menos tres incidencias de aristas y la suma de longitudes de bordes es 2m. Una arista puente aparece dos veces en el borde de una misma cara.

En un bipartito simple conexo sin triángulos los bordes tienen al menos cuatro incidencias, dando m≤2n−4.

Las mismas cotas valen para grafos simples planares no necesariamente conexos con n≥3: podemos unir componentes sin cruces hasta obtener un conexo; para el caso bipartito se pueden intercambiar los nombres de las dos partes de cada componente al conectarlas. Son condiciones necesarias. Cumplir una cota no construye un dibujo ni prueba planaridad.

Kuratowski afirma que un grafo finito es planar si y solo si no contiene una subdivisión de K₅ ni de K₃,₃. Subdividir una arista la reemplaza por un camino con nuevos vértices internos, distintos de los usados en otros reemplazos. Se enuncia aquí este resultado estructural; la cota de aristas no constituye su demostración.

El teorema de cuatro colores asegura como máximo cuatro para grafos planares. También se enuncia, sin pretender deducirlo de Euler. Euler sí permite una prueba elemental de seis colores: todo subgrafo simple planar no vacío tiene algún vértice de grado como máximo cinco; lo quitamos, repetimos y coloreamos al reconstruir en orden inverso.

Esa prueba por sí sola ofrece seis, no cuatro.

Las propiedades no se confunden: K₄ es planar y necesita cuatro colores; un árbol es planar y bipartito pero puede no tener emparejamiento perfecto; K₃,₃ es bipartito y tiene perfecto, pero no es planar. Cada pregunta requiere su propia condición.