Sufficient condition for this "intersection" graph to be connected

Question

On page 13 of this paper, the author claims that the graph defined in Lemma 6.1 is connected.

He defines $G=(V,E)$ where $V=\{A \subset [t+2r]: |A|=t+r\}$ and two vertices $A,B$ are adjacent if $|A \cap B|=t$. Then he shows that if two vertices $A,B$ are such that $|A \Delta B|=2$, then $A,B$ are connected by a path. Hence, he concludes, the graph G is connected.

Why is this sufficient to show that the entire graph is connected? I cannot see the reason why this should suffice, unless I am missing something extremely obvious.

Thanks

Answer 1

Suppose $A$ and $B$ are subsets of size $t+r$ with $|A\Delta B|=2(k-1)$ for some $k\geq 2$. By relabelling, we may assume without loss of generality that $A=\{1,2,\ldots,t+r\}$ and $B=\{k,k+1,\ldots,t+r+k-1\}$.

The case $k=2$, has already been handled by the author. Suppose that $k\geq 3$ and that $B$ and $C$ are connected by a path for any $C$ with $|B\Delta C| \leq 2(k-2).$

Consider $C=(2,3,\ldots,t+r+1)$. Then $|A\Delta C|=2$ and $|B\Delta C|=2(k-2)$. Hence there is a path from $A$ to $C$ and a path from $C$ to $B$, and so a path from $A$ to $C$.

Answer 2

Consider $A$ and $B$ in $V$ so that $A \backslash B = \{a_1, a_2, \dots, a_k\}$ and $B \backslash A = \{b_1, b_2, \dots, b_k\}$. Then consider the sequence of sets $A_0, A_1, \dots, A_k$ so that $A_0 = A$, and $A_i = (A_{i-1}\backslash \{a_i\}) \cup \{b_i\}$ for $i=1,2,\dots,k$. Thus $A_k = B$. Then $|A_{i-1} \Delta A_{i}| = 2$, so as already proven, there is an edge from $A_{i-1}$ to $A_i$ for all $i=1,2,\dots,k$. Thus $A_0 A_1 \dots A_k$ is a path in $G$ from $A$ to $B$, and $G$ is connected.