 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 compareBoth 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 provesThe equal total size is useful here: no large-count threshold or comparison of unequal multiplicities is needed.