Dans cette section, nous allons examiner une autre condition nécessaire pour qu'un graphe soit Eulérien. Il s'agit de la parité des sommets du graphe. Voici d'abord la définition de parité :
La relation entre la parité des sommets d'un graphe et le fait que le graphe soit Eulérien est exprimé par le théorème suivant :
Avant de prouver ce théorème, regardons les conséquences sur le graphe
représentant la ville de Königsberg. Les degrés des sommets de ce
graphe sont ,
,
et
respectivement. Il y a quatre
sommets impairs. Par conséquent, la ville de Königsberg n'est pas un
graphe Eulérien, ce qui explique pourquoi les citoyens de Königsberg
étaient n'arrivaient pas à trouver de chaîne appropriée.
Similairement, les degrés des sommets du graphe représentant
l'enveloppe sont ,
,
,
,
et
.
Il y a deux sommets impairs. Le théorème ne nous
donne pas le droit de conclure que l'enveloppe est Eulérienne, car il
s'agit uniquement d'une condition nécessaire. Il est important de ne
pas renverser la flèche d'implication.
Attaquons maintenant la preuve. Ce sera encore une preuve par contradiction.
Preuve :Supposons donc le contraire, à savoir qu'il existe un graphe Eulérien
dont le nombre de sommets impairs n'est ni ni
.
Le graphe est Eulérien. La définition nous indique qu'il existe
une chaîne
telle que
,
et
.
Regardons un sommet autre que et
dans cette chaîne.
Ce même sommet peut éventuellement exister plusieurs fois dans la
chaîne. Chaque occurrence d'un tel sommet, disons
, est entourée
d'arêtes
. Les deux arêtes
et
apportent donc une contribution de
au degré de
. Le degré de
est donc forcément pair.
Pour ce qui concerne et
, nous allons distinguer
deux cas. Dans le premier cas,
et
dans le deuxième cas
.
Premier cas (
) : la contribution de
au
degré de
est de
et celle de
au degré de
est aussi de
. Les degrés de
et
sont
donc forcément impairs.
Il existe par conséquent exactement deux sommets impairs.
Deuxième cas () : La contribution de
au
degré de
est
et celle de
au degré de
est aussi de
. La contribution totale au degré de
est donc
. Le degré de
est donc pair. Il n'existe par
conséquent aucun sommet impair. height4pt width4pt
En fait, la preuve nous aide pour trouver une chaîne Eulérienne dans un graphe ayant deux sommets impairs (comme l'enveloppe par exemple). La chaîne doit commencer dans un sommet impair et se terminer dans un autre sommet impair. C'est pourquoi il est nécessaire de commencer dans l'un des sommets du bas de la figure 6.2.