Graphs

(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$.

Suppose that $\Gamma$ is not connected and let $S'$ be one of its connected components. The set $S'' = S - S'$ is non-empty by Prop. 1, (i) and no element of $S'$ is joined to any element of $S''$ by Prop. 1, (iii).

Suppose now that $\Gamma$ is connected and let $(S', S'')$ be a partition with the stated property. By Prop. 1, (iv), the set $S'$ contains at least one connected component, so $S' = S$ and $S'' = \varnothing$, a contradiction.

The condition is sufficient by Prop. 1, (iv). It is necessary by Prop. 1, (iii).

(i) If $\Gamma$ has at least one vertex, it has a terminal vertex. (ii) If $\Gamma$ has at least two vertices, there is a partition $(S', S'')$ of its set of vertices into two non-empty subsets such that two distinct vertices that both belong to $S'$ or both belong to $S''$ are never joined.

Suppose that $\Gamma$ has at least one vertex and let $(x_0, \ldots, x_n)$ be an injective path of maximal length in $\Gamma$. The vertex $x_0$ cannot be joined to a vertex $y$ distinct from $x_0, x_1, \ldots, x_n$, since otherwise there would exist an injective path in $\Gamma$ of length $n + 1$, namely $(y, x_0, \ldots, x_n)$. The vertex $x_0$ is not joined to any vertex $x_i$ with $2 \leq i \leq n$, since otherwise $(x_0, x_1, \ldots, x_i)$ would be a circuit in the forest $\Gamma$. Thus, $x_0$ is terminal.

We shall prove (ii) by induction of the number $m$ of vertices of $\Gamma$, the case $m = 2$ being trivial. Suppose then that $m \geq 3$ and that assertion (ii) is proved for graphs with $m - 1$ vertices. Let $a$ be a terminal vertex of $\Gamma$ (cf. (i)). We apply the induction hypothesis to the full subgraph of $\Gamma$ whose vertices are the vertices $x \neq a$ of $\Gamma$. Thus, there exist two non-empty disjoint subsets $S'_1$ and $S''_1$ of $S$ with $S'_1 \cup S''_1 = S - \{a\}$, and such that two distinct vertices in $S'_1$ (resp. $S''_1$) are never joined. Since $a$ is joined to at most one vertex of $\Gamma$, we can suppose for example that it is not joined to any vertex in $S'_1$. The partition $(S'_1, S''_1 \cup \{a\})$ then has the required property. Q.E.D.

For any integer $n \geq 1$, denote by $A_n$ the graph whose vertices are the integers $1, 2, \ldots, n$ and whose edges are the pairs $\{i, j\}$ with $i - j = \pm 1$:

A graph $\Gamma$ is said to be a chain of length $m \geq 0$ if it is isomorphic to $A_{m+1}$. This is equivalent to the existence in $\Gamma$ of an injective path $(x_0, \ldots, x_m)$ containing all the vertices, the vertices $x_i$ and $x_j$ not being joined if $|i - j| > 1$.

Suppose that the graph $\Gamma$ is a chain $(x_0, \ldots, x_m)$ with the properties listed before the statement of Prop. 3. It is clear that any vertex of $\Gamma$ is joined to at most two vertices. If $i < j$ the path $(x_i, \ldots, x_j)$ extracted from the path $(x_0, \ldots, x_m)$ joins $x_i$ to $x_j$; thus, $\Gamma$ is connected. Finally, let $(x_{p_1}, \ldots, x_{p_n})$ be a circuit in $\Gamma$, and let $p_k$ be the smallest of the distinct integers $p_1, \ldots, p_n$. There exist distinct indices $i$ and $j$ such that $x_{p_k}$ is joined to $x_{p_i}$ and $x_{p_j}$: this follows from the definition of a circuit. Since $p_k < p_i$ and $p_k < p_j$, we necessarily have $p_i = p_j = p_k + 1$, which is a contradiction since $p_1, \ldots, p_n$ are distinct. Thus, there is no circuit in $\Gamma$.

Conversely, let $\Gamma$ be a tree with no ramification point and with a finite non-zero number of vertices, and let $(x_0, \ldots, x_m)$ be an injective path of maximal length in $\Gamma$. Denote by $T$ the set of vertices other than $x_0, \ldots, x_m$. A vertex $b \in T$ cannot be joined to any vertex $x_i$, for we would have either

a) $i = 0$, but then $(b, x_0, \ldots, x_m)$ would be an injective path of length $m + 1$ in $\Gamma$, or b) $i = m$, but then $(x_0, \ldots, x_m, b)$ would be an injective path of length $m + 1$ in $\Gamma$, or c) $0 < i < m$, but then $x_i$ would be joined to three distinct vertices $x_{i-1}$, $x_{i+1}$ and $b$.

Since $\Gamma$ is connected, $T$ is empty by Cor. 1 of Prop. 1. Moreover, if there were $i, j$ with $j - i > 1$ and $x_i, x_j$ joined, there would be a circuit $(x_i, x_{i+1}, \ldots, x_j)$ in $\Gamma$. Thus, $\Gamma$ is a chain. Q.E.D.