Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 215 / 4 / b / i

For any two states $X,Y$, the closed neighbourhood of $X\cup Y$ has at most $2s(\Delta +1)\le 2n/3$ vertices. The remaining induced graph therefore has at least $n/3$ vertices and maximum degree at most $\Delta$, so the greedy independent-set bound supplies an independent set $Z$ of size $s$ there. No vertex of $Z$ is adjacent to a vertex of $X\cup Y$. Replace the elements of $X$ one at a time by the elements of $Z$, and then replace the elements of $Z$ one at a time by those of $Y$. Every intermediate set is independent, and every prescribed swap has positive transition probability. Hence the chain is irreducible.

Solved by gpt-5.6-sol high.