La première propriété que nous allons examiner est la connexité du graphe.
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 grapheest connexe si et seulement si
, il existe une chaîne entre
et
.
Avec ces informations, attaquons la preuve :
Preuve :Supposons que l'énoncé soit faux, à savoir, qu'il existe un graphe
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
telle que
,
et
.
Comme on a supposé non connexe, alors
, sans chaîne entre
et
.
Nous les appelons
et
et non pas
et
comme dans la définition de la connexité pour ne pas confondre
avec les sommets
et
de la définition de graphe Eulérien.
Puisque la chaîne contient tous les sommets du graphe, elle contient
forcément les deux sommets
et
. Disons que
est le même
sommet que
et
est le même sommet que
. On peut donc
écrire la chaîne Eulérienne de la manière suivante :
Examinons la sous-chaîne
de
. Une
sous-chaîne d'une chaîne étant une chaîne,
est bien une chaîne entre
et
. Mais une des implications de notre supposition est qu'il
n'existe pas de chaîne entre
et
, 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