= Solution
Write $\forall_{\mathcal U}x\,\varphi(x)$ to mean $\{x:\varphi(x)\}\in\mathcal U$. For each $x$, exactly one of the red-neighbour set $R_x$ and the blue-neighbour set $B_x$ belongs to $\mathcal U$. Applying the ultrafilter dichotomy once more to
$$
\{x:R_x\in\mathcal U\}
$$
shows that exactly one of
$$
\forall_{\mathcal U}x\,\forall_{\mathcal U}y
\ (xy\text{ is red}),
\qquad
\forall_{\mathcal U}x\,\forall_{\mathcal U}y
\ (xy\text{ is blue})
$$
holds. They cannot both hold because the two outer sets are complementary; the diagonal causes no problem because a nonprincipal ultrafilter contains no singleton.
Assume the red statement and put $X=\{x:R_x\in\mathcal U\}\in\mathcal U$. Choose $x_1\in X$. Recursively choose
$$
x_n\in X\cap\bigcap_{i<n}R_{x_i}
$$
outside the finitely many previously chosen points. Every set in this finite intersection belongs to $\mathcal U$, so a choice is always possible. Then $M=\{x_1,x_2,\ldots\}$ is infinite and all of its edges are red.
Back to article page
