Connectedness of fixed-occupancy exclusion sectors

A finite connected graph has a spanning tree: start with one vertex and, while the current vertex set is not $V$, add an edge from that set to its complement together with the new endpoint. Such an edge exists because otherwise no path could join the current set to its complement. Finiteness makes this process terminate; each added edge attaches one new vertex, so the resulting spanning subgraph is connected and has no cycle.

We prove by induction on the number of vertices that the $k$-element subsets of any finite tree are connected for every admissible $k$. The assertion holds for a one-vertex tree, since its $0$- and $1$-element subset graphs each have one vertex. For a tree $T$ with at least two vertices, choose a simple path of maximum length; either endpoint is a leaf, because an additional neighbor outside the path would extend it, while an additional neighbor on the path would create a cycle. Let $v$ be a leaf. Removing a leaf leaves a connected acyclic graph, hence a smaller tree: the unique path between two remaining vertices cannot have the leaf as an interior vertex. If two configurations $A,B$ have the same occupancy at $v$, removing $v$ leaves two subsets of the same cardinality in $T-v$; by induction a sequence of legal moves there connects them, and the same moves in $T$ keep the occupancy at $v$ fixed.

Suppose $v\in A$ and $v\mathrm{\notin }B$. Since $k<m$, choose a vacant vertex $w\mathrm{\notin }A$ and let $v=v_0,v_1,\dots ,v_r=w$ be the unique simple path in $T$ from $v$ to $w$. Existence follows from connectedness, and two distinct simple paths would contain a cycle, so the path is unique. Let $j$ be the first index with $v_j\mathrm{\notin }A$; then $v_0,\dots ,v_{j-1}$ are occupied. Move the particle at $v_{j-1}$ to the vacancy $v_j$, then the particle at $v_{j-2}$ to the new vacancy $v_{j-1}$, and continue until the particle at $v_0$ has moved to $v_1$. These are legal edge moves and leave $v$ vacant. The resulting configuration and $B$, restricted to $T-v$, both have $k$ particles; induction connects them without using $v$.

Suppose $v\mathrm{\notin }A$ and $v\in B$. Since $k>0$, choose an occupied vertex $w\in A$ and use the unique path $v=v_0,\dots ,v_r=w$. Let $j$ be the first index with $v_j\in A$; all earlier vertices are vacant. Move the particle from $v_j$ to $v_{j-1}$, then from $v_{j-1}$ to $v_{j-2}$, and continue until $v_0=v$ is occupied. The moves are legal along the path. The resulting configuration and $B$, restricted to $T-v$, both have $k-1$ particles; induction connects them without using $v$. This proves the claim for trees, including the cases $k=0$ and $k=m$ already covered by their singleton configuration graphs.

Apply step 1.1 to $G$ and let $T$ be a spanning tree. Every move along an edge of $T$ is also an allowed move in $G$. steps 3.1 and 3.2 therefore connect any two $k$-element subsets using edges of $G$, so ${\mathcal{C}}_k(G)$ is connected.