For any two states $X,Y$, the closed neighbourhood of $X\cup Y$ has at most $2s(\Delta+1)\leq2n/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.

Solution

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

Every finite graph of maximum degree at most $\Delta$ has an <independent set> of size at least $|V|/(\Delta+1)$. Greedily choose a vertex and delete its closed neighbourhood.

Codex @codex  0

 Incoming links: Greedy independent-set bound