Connexité

La première propriété que nous allons examiner est la connexité du graphe.

Théorème 6.1   Un graphe Eulérien est forcément connexe.

Voici d'autres façons de dire la même chose :

• Tout graphe Eulérien est connexe,
• Si un graphe est Eulérien, alors il est connexe,
• $G$ Eulérien $\Rightarrow$ $G$ connexe.
• Si un graphe n'est pas connexe, alors il n'est pas Eulérien,
• $G$ est connexe est une condition nécessaire pour que $G$ soit Eulérien.

Comment prouver un tel théorème ? Il y a plusieurs façons. Nous avons déjà vu (Section 5.1) une preuve par induction. Ce type de preuve n'est pas adapté à ce théorème. À la place, nous allons utiliser un raisonnement par l'absurde. L'idée d'une telle preuve est de supposer que l'énoncé est faux, puis de montrer que cette supposition conduit à une contradiction. Puisque la logique ne peut pas être contradictoire, c'est la supposition qui est fausse, et par conséquent l'énoncé est vrai.

La première chose à faire pour prouver un théorème comme celui-ci est d'examiner les définitions des concepts qu'il fait intervenir. Ici, il faut donc examiner la définition de ``Eulérien'' et de ``connexité''. La définition de ``Eulérien'' se trouve dans le section précédente. Rappelons la définition de ``connexité'':

Un graphe $G$ est connexe si et seulement si $\forall s_1, s_2 \in V(G)$, il existe une chaîne entre $s_1$ et $s_2$.

Avec ces informations, attaquons la preuve :

Preuve :Supposons que l'énoncé soit faux, à savoir, qu'il existe un graphe $G$ Eulérien non connexe. (Il est important de réaliser que cette phrase est le contraire de l'énoncé).

Maintenant, il faut examiner les conséquences de cette supposition. Le graphe est Eulérien. Par définition de Eulérien, on sait qu'il existe une chaîne
$C = s_1, e_1, s_2, e_2, \ldots, s_m, e_m, s_{m+1}$ telle que $\{s_1, s_2, \ldots, s_m, s_{m+1}\} = V(G)$,
$\{e_1, e_2, \ldots, e_m\} = E(G)$ et $\vert E(G)\vert = m$.

Comme on a supposé $G$ non connexe, alors $\exists t_1, t_2 \in V(G)$, sans chaîne entre $t_1$ et $t_2$. Nous les appelons $t_1$ et $t_2$ et non pas $s_1$ et $s_2$ comme dans la définition de la connexité pour ne pas confondre avec les sommets $s_1$ et $s_2$ de la définition de graphe Eulérien.

Puisque la chaîne $C$ contient tous les sommets du graphe, elle contient forcément les deux sommets $t_1$ et $t_2$. Disons que $t_1$ est le même sommet que $s_i$ et $t_2$ est le même sommet que $s_j$. On peut donc écrire la chaîne Eulérienne de la manière suivante : $C = s_1, e_1, s_2, e_2, \ldots, t_1, e_i, \ldots, e_{j-1}, t_2, \ldots, s_m, e_m, s_{m+1}$

Examinons la sous-chaîne $C' = t_1, e_i, \ldots, e_{j-1}, t_2$ de $C$. Une sous-chaîne d'une chaîne étant une chaîne, $C'$ est bien une chaîne entre $t_1$ et $t_2$. Mais une des implications de notre supposition est qu'il n'existe pas de chaîne entre $t_1$ et $t_2$, ce qui donne une contradiction.

Notre supposition qu'il existe un graphe Eulérien non connexe est donc fausse. Nous pouvons alors conclure que tout graphe Eulérien est connexe. height4pt width4pt