= Solution
Suppose a <first-order sentence> $\theta$ defined the <bipartite graphs>, equivalently the 2-colourable graphs. Let $q$ be its <quantifier rank> and $r=3^q$. Choose an odd integer $N>2r+1$, and compare
$$
A=C_{2N},\qquad B=C_N\sqcup C_N.
$$
Both have $2N$ vertices. Every marked radius-$r$ neighbourhood in either graph is a path with $2r+1$ vertices and its middle vertex marked: the choice of $N$ prevents the ball from wrapping around a cycle. Thus every vertex has exactly the same neighbourhood type in both graphs, and that type occurs $2N$ times in each. Any bijection of their universes meets the <Hanf locality lemma> hypothesis.
Therefore $A$ and $B$ agree on $\theta$. But $A$ is an even cycle and is bipartite, whereas $B$ contains odd cycles and is not bipartite. This contradiction proves
$$
\boxed{\text{No first-order sentence defines 2-colourability, even on finite graphs.}}
$$
The equal total size is useful here: no large-count threshold or comparison of unequal multiplicities is needed.
Back to article page
