Graphes

(i) Pour tout $\alpha$ dans $L$, le graphe $\Gamma_\alpha$ est connexe.

(ii) Si $\Gamma' = (A', S')$ est un sous-graphe connexe de $\Gamma$, il existe $\alpha$ dans $L$ tel que $S' \subset S_\alpha$.

(iii) Pour $\alpha \neq \beta$, aucun élément de $S_\alpha$ n’est lié dans $\Gamma$ à un élément de $S_\beta$ (autrement dit, toute arête de $\Gamma$ est une arête de l’un des $\Gamma_\alpha$).

(iv) Soit $(S'_\lambda)_{\lambda \in M}$ une partition de $S$ telle que pour $\lambda \neq \mu$ aucun élément de $S'_\lambda$ ne soit lié dans $\Gamma$ à un élément de $S'_\mu$; alors chacun des ensembles $S'_\lambda$ est réunion de composantes connexes de $\Gamma$.

(i) Soient $\alpha$ dans $L$, et $a, b$ dans $S_\alpha$. Il existe donc un chemin $c = (x_0, \ldots, x_n)$ joignant $a$ à $b$ dans $\Gamma$; pour tout $i$ tel que $0 \leq i \leq n$, le chemin $(x_0, \ldots, x_i)$ joint $a$ à $x_i$ dans $\Gamma$, d’où $x_i \in S_\alpha$; finalement, $c$ est un chemin dans $\Gamma_\alpha$ joignant $a$ à $b$. Par suite, $\Gamma_\alpha$ est connexe.

(ii) Soient $\Gamma' = (A', S')$ un sous-graphe connexe non vide de $\Gamma$, $a$ un élément de $S'$, $S_\alpha$ la composante connexe de $\Gamma$ contenant $a$. Pour tout $b$ dans $S'$, il existe un chemin $c$ joignant $a$ à $b$ dans $\Gamma'$, et a fortiori dans $\Gamma$. Par suite, on a $S' \subset S_\alpha$.

(iii) Étant donnés $\alpha$ et $\beta$ distincts dans $L$, et des sommets $a \in S_\alpha$ et $b \in S_\beta$, il n’existe aucun chemin joignant $a$ à $b$, et en particulier aucune arête ne joint $a$ à $b$.

(iv) Soient $a$ dans $S'_\lambda$, et $S_\alpha$ la composante connexe de $\Gamma$ contenant $a$; pour tout $b$ dans $S_\alpha$, il existe un chemin $(x_0, \ldots, x_n)$ joignant $a$ à $b$ dans $\Gamma$. Si $i$ est un entier tel que $0 \leq i < n$ et $x_i \in S'_\lambda$, on a $x_{i+1} \in S'_\lambda$ puisque $x_i$ est lié à $x_{i+1}$; par récurrence, on a donc $x_i \in S'_\lambda$ pour $0 \leq i \leq n$ et en particulier $b = x_n$ est dans $S'_\lambda$. On a donc $S_\alpha \subset S'_\lambda$.

Supposons $\Gamma$ non connexe et soit $S'$ une de ses composantes connexes; l’ensemble $S'' = S - S'$ est non vide d’après la prop. 1, (i) et aucun élément de $S'$ n’est lié dans $\Gamma$ à un élément de $S''$ d’après la prop. 1, (iii).

Supposons $\Gamma$ connexe et soit $(S', S'')$ une partition ayant la propriété de l’énoncé. D’après la prop. 1, (iv), l’ensemble $S'$ contient au moins une composante connexe, d’où $S' = S$ et $S'' = \varnothing$, ce qui est contradictoire.

La condition est suffisante d’après la prop. 1, (iv). Elle est nécessaire d’après la prop. 1, (iii).

Supposons qu’il existe au moins un sommet dans $\Gamma$, et soit $(x_0, \ldots, x_n)$ un chemin injectif de longueur maximale dans $\Gamma$. Le sommet $x_0$ ne peut être lié à un sommet $y$ distinct de $x_0, x_1, \ldots, x_n$ sinon il existerait dans $\Gamma$ un chemin injectif de longueur $n + 1$, à savoir $(y, x_0, \ldots, x_n)$. Le sommet $x_0$ n’est lié à aucun sommet $x_i$ avec $2 \leq i \leq n$, sinon $(x_0, x_1, \ldots, x_i)$ serait un circuit dans la forêt $\Gamma$. Donc $x_0$ est terminal.

On démontrera (ii) par récurrence sur le nombre $m$ de sommets de $\Gamma$, le cas $m = 2$ étant trivial. Supposons donc $m \geq 3$ et l’assertion (ii) prouvée pour les graphes à $m - 1$ sommets. Soit $a$ un sommet terminal de $\Gamma$ (cf. (i)). Appliquons l’hypothèse de récurrence au sous-graphe plein de $\Gamma$ ayant pour sommets les sommets $x \neq a$ de $\Gamma$; il existe donc deux parties non vides et disjointes $S'_1$ et $S''_1$ de $S$ avec $S'_1 \cup S''_1 = S - \{a\}$, telles que deux sommets distincts de $S'_1$ (resp. $S''_1$) ne soient jamais liés. Comme $a$ est lié à un sommet au plus de $\Gamma$, on peut supposer par exemple qu’il n’est lié à aucun sommet de $S''_1$; la partition $(S'_1, S''_1 \cup \{a\})$ de $S$ répond alors à la question. C.Q.F.D.

Pour tout entier $n \geq 1$, on note $A_n$ le graphe dont les sommets sont les entiers $1, 2, \ldots, n$ et les arêtes les parties $\{i, j\}$ avec $i - j = \pm 1$:

On dit qu’un graphe $\Gamma$ est une chaîne de longueur $m \geqslant 0$ s’il est isomorphe à $A_{m+1}$; ceci équivaut à l’existence dans $\Gamma$ d’un chemin injectif $(x_0, \ldots, x_m)$ contenant tous les sommets, les sommets $x_i$ et $x_j$ n’étant pas liés lorsque $|j - i| > 1$.

Supposons que le graphe $\Gamma$ soit une chaîne $(x_0, \ldots, x_m)$ avec les propriétés énumérées avant l’énoncé de la prop. 3. Il est clair qu’un sommet de $\Gamma$ est lié à deux sommets au plus. Pour $i < j$, le chemin $(x_i, \ldots, x_j)$ extrait du chemin $(x_0, \ldots, x_m)$ joint $x_i$ à $x_j$; donc $\Gamma$ est connexe. Enfin, soit $(x_{p_1}, \ldots, x_{p_n})$ un circuit dans $\Gamma$; soit $p_k$ le plus petit parmi les entiers distincts $p_1, \ldots, p_n$. Il existe $i$ et $j$ distincts tels que $x_{p_k}$ soit lié à $x_{p_i}$ et $x_{p_j}$: cela résulte de la définition d’un circuit. Comme on a $p_k < p_i$ et $p_k < p_j$, on a nécessairement $p_i = p_j = p_k + 1$, ce qui est contradictoire puisque $p_1, \ldots, p_n$ sont distincts. Il n’y a donc aucun circuit dans $\Gamma$.

Réciproquement, soit $\Gamma$ un arbre sans point de ramification, à un nombre fini non nul de sommets, et soit $(x_0, \ldots, x_m)$ un chemin injectif de longueur maximale dans $\Gamma$. Notons $T$ l’ensemble des sommets autres que $x_0, \ldots, x_m$. Un sommet $b \in T$ ne peut être lié à un sommet $x_i$; il y a en effet trois possibilités :

a) $i = 0$, mais alors $(b, x_0, \ldots, x_m)$ serait un chemin injectif de longueur $m + 1$ dans $\Gamma$; b) $i = m$, mais alors $(x_0, \ldots, x_m, b)$ serait un chemin injectif de longueur $m + 1$ dans $\Gamma$; c) $0 < i < m$, mais alors $x_i$ serait lié aux trois sommets distincts $x_{i-1}, x_{i+1}$ et $b$.

Comme $\Gamma$ est connexe, $T$ est vide d’après le cor. 1 de la prop. 1. Par ailleurs, s’il existait $i, j$ tels que $j - i > 1$ et que $x_i, x_j$ soient liés, on aurait un circuit $(x_i, x_{i+1}, \ldots, x_j)$ dans $\Gamma$. Donc $\Gamma$ est une chaîne.

Exercises