Proposition 1

Let $\Gamma = (A, S)$ be a graph and $(S_\alpha)_{\alpha \in L}$ its family of connected components. Denote by $\Gamma_\alpha$ the full subgraph of $\Gamma$ having $S_\alpha$ as its set of vertices.

(i) For any $\alpha$ in $L$, the graph $\Gamma_\alpha$ is connected. (ii) If $\Gamma' = (A', S')$ is a connected subgraph of $\Gamma$, there exists $\alpha$ in $L$ such that $\Gamma' \subset \Gamma_\alpha$. (iii) If $\alpha \neq \beta$, no element of $S_\alpha$ is joined in $\Gamma$ to any element of $S_\beta$ (equivalently, every edge of $\Gamma$ is an edge of one of the $\Gamma_\alpha$). (iv) Let $(S'_\lambda)_{\lambda \in M}$ be a partition of $S$ such that, if $\lambda \neq \mu$, no element of $S'_\lambda$ is joined in $\Gamma$ to any element of $S'_\mu$; then each of the sets $S'_\lambda$ is a union of connected components of $\Gamma$.

(i) Let $\alpha$ be in $L$ and $a$ and $b$ be in $S_\alpha$. Then there exists a path $c = (x_0, \ldots, x_n)$ joining $a$ and $b$ in $\Gamma$. For any $i$ with $0 \leq i \leq n$, the path $(x_0, \ldots, x_i)$ joins $a$ to $x_i$ in $\Gamma$, so $x_i \in S_\alpha$. Thus, $c$ is a path in $\Gamma_\alpha$ joining $a$ and $b$. It follows that $\Gamma_\alpha$ is connected.

(ii) Let $\Gamma' = (A', S')$ be a non-empty connected subgraph of $\Gamma$, let $a$ be an element of $S'$ and let $S_\alpha$ be the connected component of $S$ containing $a$. For any $b$ in $S'$, there exists a path $c$ joining $a$ and $b$ in $\Gamma'$, and a fortiori in $\Gamma$. It follows that $S' \subset S_\alpha$.

(iii) Given distinct elements $\alpha$ and $\beta$ of $L$, and vertices $a \in S_\alpha$ and $b \in S_\beta$, there is no path joining $a$ and $b$, and in particular no edge joining $a$ and $b$.

(iv) Let $a$ be in $S'_\lambda$ and let $S_\alpha$ be the connected component of $\Gamma$ containing $a$. Then, for any $b$ in $S_\alpha$, there exists a path $(x_0, \ldots, x_n)$ joining $a$ and $b$ in $\Gamma$. If $i$ is an integer such that $0 \leq i < n$ and if $x_i \in S'_\lambda$, then $x_{i+1} \in S'_\lambda$ since $x_i$ is joined to $x_{i+1}$. It follows by induction that $x_i \in S'_\lambda$ for $0 \leq i \leq n$, and in particular that $b = x_n$ is in $S'_\lambda$. Thus, $S_\alpha \subset S'_\lambda$.