Proposition 2

Let $\Gamma = (A, S)$ be a forest having only a finite number of vertices.

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