Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2022/ii/paper-3/17f/d/solution
Past exam of the mathematics course of the University of Cambridge 2022 ii Paper 3 17F d Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
Colour every vertex independently red or blue with probability . Fix a vertex and enumerate infinitely many distinct neighbours . The probability that all neighbours after are red isTaking the countable union over , the probability that has only finitely many blue neighbours is zero. The same argument with the colours exchanged shows that the probability of only finitely many red neighbours is zero.
The vertex set is countable, so the union of these two null events over all vertices still has probability zero. Thus with probability one every vertex has infinitely many neighbours of each colour. Taking and to be the two colour classes gives an unfriendly partition. This is the random unfriendly partition of a countable infinite-degree graph.
New to topics? Read the docs here!