Grafos bipartitos y argumentos de 2-coloración

La idea de colorear para separar

Cuando un problema pide demostrar que un conjunto de objetos puede dividirse en dos grupos con cierta propiedad de compatibilidad —o demostrar que esa división es imposible— la herramienta más poderosa de la teoría de grafos es la 2-coloración. La idea es simple: construye un grafo donde los vértices son los objetos y las aristas conectan objetos "incompatibles"; luego pregunta si ese grafo es bipartito.

Un grafo es bipartito si sus vértices pueden colorearse con dos colores (digamos blanco y negro) de modo que ninguna arista conecte dos vértices del mismo color. Esto es exactamente una 2-coloración válida. El problema de verificar si un grafo es bipartito se reduce a verificar si tiene ciclos de longitud impar.

Esta técnica resuelve, entre otros, todos los problemas de tableros de ajedrez: ¿puede cubrirse con dominós? ¿Con triominós en L? ¿Con ciertas piezas? La coloración blanco-negro del tablero codifica la bipartición natural, y la pregunta de recubrimiento se convierte en una pregunta de matching en un grafo bipartito.

En la Olimpiada Iberoamericana 2003 se planteó un problema equivalente a: "¿puede 2-colorearse este hipérgrado de tal forma que ningún subconjunto prohibido sea monocromático?" Detrás de la solución había exactamente el Teorema de Caracterización de Grafos Bipartitos, aplicado a un grafo auxiliar construido a partir de los conjuntos prohibidos.

Teorema de caracterización y su prueba completa

Un grafo $G$ es bipartito si existe una partición $V(G) = A \cup B$ con $A \cap B = \emptyset$ tal que toda arista de $G$ conecta un vértice en $A$ con un vértice en $B$. La pareja $(A, B)$ se llama bipartición de $G$.

Teorema: $G$ es bipartito si y solo si $G$ no contiene ciclos de longitud impar.

**Demostración ($\Rightarrow$):** Sea $G$ bipartito con bipartición $(A,B)$. Sea $C = v_0, v_1, \ldots, v_{k-1}, v_0$ un ciclo de longitud $k$. Las aristas alternan entre $A$ y $B$: si $v_0 \in A$, entonces $v_1 \in B$, $v_2 \in A$, etc. En general $v_i \in A$ si $i$ es par y $v_i \in B$ si $i$ es impar. Para que el ciclo cierre, $v_0 \in A$ y $v_{k-1}$ deben estar en lados opuestos, es decir $k-1$ impar, o sea $k$ par. Todo ciclo tiene longitud par. $\square$

**Demostración ($\Leftarrow$):** Supongamos que $G$ no contiene ciclos de longitud impar. Podemos asumir sin pérdida de generalidad que $G$ es conexo (si no, aplicamos el argumento a cada componente). Fijamos un vértice $r \in V$. Para cada $v \in V$, definimos $d(r,v)$ como la distancia (longitud del camino más corto) de $r$ a $v$. Sea $A = \{v : d(r,v) \text{ es par}\}$ y $B = \{v : d(r,v) \text{ es impar}\}$.

Afirmamos que toda arista $\{u,v\} \in E$ satisface $u \in A$ y $v \in B$ o viceversa. Supongamos por contradicción que $u, v \in A$, es decir, $d(r,u)$ y $d(r,v)$ son ambos pares. Sea $P_u$ un camino más corto de $r$ a $u$ y $P_v$ uno de $r$ a $v$. Combinando $P_u$, la arista $u$-$v$, y el inverso de $P_v$, obtenemos un paseo de longitud $d(r,u) + 1 + d(r,v)$ de $r$ a $r$. Este paseo puede no ser un ciclo simple (puede repetir vértices), pero contiene un ciclo. La longitud total es par $+$ 1 $+$ par $=$ impar. Luego el paseo contiene un ciclo de longitud impar, contradicción. El caso $u, v \in B$ es análogo. Por tanto $(A, B)$ es una bipartición válida. $\square$

Problemas de tableros: la coloración de ajedrez

El tablero $m \times n$ con la coloración de ajedrez define naturalmente un grafo bipartito $G$: los vértices son los casilleros, y dos casilleros son adyacentes si comparten un lado. Los casilleros blancos forman el conjunto $A$ y los negros el conjunto $B$.

Problema clásico: ¿Puede cubrirse un tablero $8 \times 8$ al que se le quitan las dos esquinas opuestas con dominós $1 \times 2$? Respuesta: no. Las dos esquinas opuestas tienen el mismo color (por ejemplo ambas blancas). Al quitarlas, quedan $32$ casilleros blancos menos $2 = 30$ casilleros blancos y $32$ casilleros negros. Cada dominó cubre exactamente un casillero blanco y uno negro. Un recubrimiento perfecto requeriría $|A| = |B|$, pero $30 \neq 32$. Imposible. $\square$

Generalización con el Teorema de Hall: Un recubrimiento del tablero por dominós corresponde a un matching perfecto en $G$. Por el Teorema de Hall, dicho matching existe si y solo si para todo $S \subseteq A$, $|N(S)| \geq |S|$. En el tablero completo $m \times n$ con $mn$ par, este matching existe (puede construirse explícitamente). El ejemplo anterior muestra que al eliminar vértices de un solo color, podemos violar la condición de Hall.

Variante con piezas en L: Una pieza en L (triominó) cubre exactamente 3 casilleros. El tablero $2^k \times 2^k$ menos un casillero cualquiera puede cubrirse con triominós en L. La prueba es por inducción: divide el tablero en cuatro cuadrantes de tamaño $2^{k-1} \times 2^{k-1}$. El casillero faltante está en uno de los cuadrantes; coloca un triominó en L en la esquina central cubriendo un casillero de cada uno de los tres cuadrantes "vacíos". Ahora cada cuadrante tiene exactamente un casillero cubierto o faltante, y la hipótesis inductiva se aplica.

Problema olímpico (Cono Sur 2009, P2): En un tablero $n \times n$ se colocan fichas en algunos casilleros. Se dice que dos casilleros son "vecinos" si comparten un lado. Se desea que ningún casillero con ficha tenga más de un vecino con ficha. Demuestra que el número máximo de fichas es $\lceil n^2 / 2 \rceil$. Solución: la condición "ningún casillero con ficha tiene más de 1 vecino con ficha" implica que el subgrafo inducido por los casilleros con fichas no tiene camino de longitud $> 1$ como componente, o sea, cada componente es $K_1$ o $K_2$. Una cota superior: el conjunto de casilleros con fichas es "casi" independiente; la coloración de ajedrez muestra que podemos tomar $\lceil n^2/2 \rceil$ casilleros de un solo color, ninguno adyacente a otro, y esta es la cota máxima.

2-coloración en problemas de partición y asignación

Más allá de los tableros, la 2-coloración resuelve problemas de partición de conjuntos. El patrón es siempre el mismo: queremos partir $n$ objetos en dos grupos $A$ y $B$ tal que cierta propiedad de "incompatibilidad" se cumpla. Definimos el grafo $G$ con los objetos como vértices y aristas entre incompatibles. Si $G$ es bipartito, la bipartición da la partición deseada; si no, la condición es imposible.

Ejemplo: coloración de hipergrafos. Sea $H = (V, \mathcal{E})$ un hipergrafo con $n$ vértices y conjuntos de aristas $E_1, E_2, \ldots, E_m \subseteq V$. Una 2-coloración de $H$ asigna a cada vértice uno de dos colores de modo que ninguna hiperarista es monocromática. El hipergrafo $H$ es 2-coloreable si y solo si existe tal coloración. Para hipergrafos donde cada hiperarista tiene exactamente 2 vértices, esto es exactamente la bipartición del grafo.

Resultado de Erdős: Todo hipergrafo $k$-uniforme (todas las hiperaristas tienen $k$ vértices) con menos de $2^{k-1}$ hiperaristas es 2-coloreable. La prueba usa el método probabilístico: una coloración aleatoria uniforme tiene probabilidad $2^{1-k}$ de que cualquier hiperarista dada sea monocromática; por la desigualdad de la unión, si $m < 2^{k-1}$ la probabilidad de que haya alguna hiperarista monocromática es menor que 1, luego existe una coloración buena.

Aplicación a torneos y competencias: Dado un torneo (grafo dirigido completo) $T$ con $n$ equipos, el grafo subyacente de $T$ es el grafo no dirigido $G$ con la misma estructura. El torneo $T$ admite una partición de los equipos en dos grupos $A$ y $B$ tal que todos los partidos $A$ vs $B$ los ganó el mismo grupo si y solo si $G$ es bipartito. Esta observación conecta la teoría de torneos con la 2-coloración.

Problema olímpico (IbAm 2007, P3, adaptado): Se tienen $n$ personas en una fiesta. Cada persona le cae "bien" o "mal" a cada otra. Se quiere dividirlas en dos grupos de tal forma que cada persona tenga más "amigos" en el otro grupo que en el suyo. Demuestra que si el grafo de amistades $G$ es tal que cada vértice tiene grado $\geq n/2$, entonces la división es posible. Solución: considera un corte $(A, B)$ que maximice el número de aristas entre $A$ y $B$. Si algún $v \in A$ tuviera más amigos en $A$ que en $B$, moverlo a $B$ aumentaría el número de aristas cruzadas, contradiciendo la maximalidad. El corte máximo da la partición deseada.

Estrategias olímpicas con 2-coloración

El arma más efectiva para usar 2-coloración en olimpiadas es identificar la relación de incompatibilidad correcta. Una mala elección de aristas no da un grafo bipartito aunque la partición exista; una buena elección hace que la bipartición sea inmediata.

Guía de identificación: (1) Si el problema habla de pares de objetos que "no pueden estar juntos", conecta esos pares con aristas. (2) Si habla de ciclos o trayectorias que deben alternarse, intenta parificar los pasos. (3) Si el problema involucra matrices o tablas con signos $+/-$, la 2-coloración puede ser la estructura detrás del signo.

Técnica de paridad: En muchos problemas de olimpiadas, la 2-coloración equivale a asignar paridades. Por ejemplo, en un proceso que cambia el estado de un vértice en cada paso, la paridad del número de pasos divide los estados en "alcanzables en número par de pasos" y "en número impar". Si el grafo es bipartito, estos dos conjuntos son exactamente la bipartición.

Argumento de imposibilidad: Para demostrar que cierta partición NO existe, basta mostrar que el grafo de incompatibilidades contiene un ciclo impar. El ciclo más corto que encontremos ya da la contradicción. Esta estrategia es particularmente limpia en olimpiadas: "el grafo tiene el siguiente ciclo impar de longitud 3/5/7, luego la partición pedida no existe".

Problema de síntesis (IbAm 2013, P2): $n$ equipos juegan un torneo de liga. Se quiere colorear los equipos de blanco y negro tal que cada partido blanco vs blanco tenga resultado diferente a cada partido negro vs negro (es decir, la relación de "ganarle a" es "cruzada" entre colores). Muestra que esto es posible si y solo si el torneo es 2-coloreable como grafo no dirigido subyacente. Aplica el Teorema de Caracterización para verificar cuándo existe tal coloración.

Resumen de la técnica: Define el grafo correcto, detecta si es bipartito mediante búsqueda de ciclos impares, y usa la bipartición como la partición pedida. Si necesitas demostrar imposibilidad, exhibe un ciclo impar explícito. Si el grafo no es conexo, aplica el argumento a cada componente.