Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 3 / 17F / c / Solution

Enumerate the vertices as $v_1,v_2,\dots$. Since every vertex has finite degree, choose increasing finite vertex sets $W_n$ whose union is $V$ and such that the closed neighbourhood of $v_i$ lies in $W_n$ whenever $i\le n$. By part (b), each finite induced graph $G[W_n]$ has an unfriendly two-colouring.

There are only two colours. Pass successively to an infinite subsequence on which the colour of $v_1$ is constant, then one on which the colour of $v_2$ is constant, and so on. The diagonal argument gives a limiting colouring in which, for every fixed finite set of vertices, all its colours agree with those in infinitely many of the finite colourings.

Fix $v_i$. Its entire finite neighbourhood lies in every sufficiently large $W_n$, and along the diagonal subsequence the colours of $v_i$ and all its neighbours eventually stabilize. The unfriendly inequality for $v_i$ in $G[W_n]$ therefore passes unchanged to the limit. This holds for every vertex, proving the unfriendly partition theorem for a countable locally finite graph.

Solved by gpt-5.6-sol high.