Existence of a certain 2-coloring of a graph There are n studio apartments in a building. Some of the apartments are connected with each other by direct phone line. Prove that it is possible to assign to each apartment a female or a male in such way that each person has direct connection with at least as many people of the opposite sex as he/she has with people the same sex.
 A: Assign the apartments in a way that maximizes the number of direct lines connecting a male to a female. Consider any tenant, assumed w.l.o.g. to be male. If he were connected to more men than women, then replacing him with a woman would increase the number of male-female connections, contradicting the assumed maximality.
By a standard "compactness" argument [*], the result can be generalized to locally finite graphs, i.e., the number of apartments may be infinite, but each one is connected to only finitely many others.
The result easily generalizes to any number of sexes. To put it in standard graph-theoretic terminology:
Theorem. Given a locally finite graph $G$ and a nonempty finite set $S$, we can find a function $f:V(G)\to S$ such that, for any $x\in V(G)$ and any $s\in S$, we have $$|\{y\in N(x):f(y)=s\}|\ge|\{y\in N(x):f(y)=f(x)\}|.$$
[*] In case anyone is interested, here is (one version of) the "compactness argument" used to get from the finite to the locally finite case. Let $F$ be the set of all functions $f:V(G)\to S$. Viewed as the Tychonoff product of copies of $S$ endowed with the discrete topology, $F$ is a compact space. For each vertex $x$, let $K_x$ be the set of all functions $f\in F$ such that the displayed inequality holds at $x$ (for all $s\in S$). Note that $K_x$ is a closed set. (The assumption of local finiteness is used here.) 
I claim the the family $\{K_x:x\in V(G)\}$ has the finite intersection property, i.e., that $\bigcap_{x\in X}K_x\ne\emptyset$ for each finite set $X\subseteq V(G)$. This follows from the finite case of the theorem, applied to the finite graph obtained by restricting $G$ to the finite set consisting of the vertices in $X$ and their neighbors. (Local finiteness is used again here.) Hence, by compactness, we have $\bigcap_{x\in V(G)}K_x\ne\emptyset$, Q.E.D.
