Existencia de una determinada 2-coloración de un gráfico.

Asigne los apartamentos de manera que maximice la cantidad de líneas directas que conectan a un hombre con una mujer. Considere a cualquier inquilino, asumiendo que el wlog es hombre. Si estuviera conectado con más hombres que mujeres, reemplazarlo con una mujer aumentaría el número de conexiones hombre-mujer, contradiciendo la maximalidad asumida.

Mediante un argumento estándar de "compacidad" [*], el resultado puede generalizarse a gráficos localmente finitos , es decir, el número de apartamentos puede ser infinito, pero cada uno está conectado a un número finito de otros.

El resultado se generaliza fácilmente a cualquier número de sexos. Para ponerlo en terminología estándar de teoría de grafos:

Teorema. Dado un gráfico localmente finito$G$y un conjunto finito no vacío$S$, podemos encontrar una función$f:V(G)\to S$tal que, para cualquier$x\in V(G)$y cualquier$s\in S$, tenemos

[*] En caso de que alguien esté interesado, aquí está (una versión de) el "argumento de compacidad" usado para pasar del caso finito al localmente finito. Dejar$F$sea ​​el conjunto de todas las funciones$f:V(G)\to S$. Visto como el producto Tychonoff de copias de$S$dotado de la topología discreta,$F$es un espacio compacto. Por cada vértice$x$, dejar$K_x$sea ​​el conjunto de todas las funciones$f\in F$tal que la desigualdad mostrada se cumple en$x$(para todos$s\in S$). Tenga en cuenta que$K_x$es un conjunto cerrado. (Aquí se utiliza la suposición de finitud local.) Afirmo que la familia$\{K_x:x\in V(G)\}$tiene la propiedad de intersección finita, es decir, que$\bigcap_{x\in X}K_x\ne\emptyset$para cada conjunto finito$X\subseteq V(G)$. Esto se sigue del caso finito del teorema, aplicado al gráfico finito obtenido al restringir$G$al conjunto finito formado por los vértices de$X$y sus vecinos. (La finitud local se usa nuevamente aquí.) Por lo tanto, por compacidad, tenemos$\bigcap_{x\in V(G)}K_x\ne\emptyset$, QED