next up previous contents index
suivant: Parité des sommets monter: Conditions nécessaires pour un précédent: Conditions nécessaires pour un   Table des matières   Index

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 :

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


next up previous contents index
suivant: Parité des sommets monter: Conditions nécessaires pour un précédent: Conditions nécessaires pour un   Table des matières   Index