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.