Argumentos de paridad usando dos colores.
La coloración bipartita es una técnica combinatoria muy poderosa que te sirve para analizar la estructura de cuadrículas, grafos y arreglos espaciales. En esencia, el método consiste en asignar una de dos propiedades (que casi siempre vas a ver como colores, como blanco y negro) a cada elemento de un conjunto, de tal forma que los elementos adyacentes o conectados siempre tengan propiedades distintas. Esto crea una estructura bipartita donde divides el conjunto de vértices $V$ en dos conjuntos disjuntos, $A$ y $B$, de modo que cada arista conecta un vértice en $A$ con uno en $B$. El ejemplo más clásico es la coloración de tablero de ajedrez estándar en una cuadrícula, donde no vas a encontrar dos cuadrados del mismo color que compartan un lado.
Esta técnica te sirve principalmente para demostrar que algo es imposible o para encontrar invariantes en sistemas dinámicos. En problemas de pavimentación, por ejemplo, un argumento de coloración bipartita te puede demostrar que no puedes cubrir cierta región con un conjunto específico de fichas si cuentas cuántas celdas hay de cada color. Si una ficha tiene que cubrir exactamente $k$ celdas negras y $m$ celdas blancas, pero la región que quieres cubrir no tiene la proporción necesaria de celdas negras y blancas, entonces pavimentarla es imposible. Esto se basa en el principio de paridad: la diferencia entre la cantidad de celdas de los dos colores suele darte una restric