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

Parité des sommets

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é :

Définition 6.2   Un sommet est pair si son degré est pair. De même un sommet est impair si son degré est impair.

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 :

Théorème 6.2   Dans un graphe Eulérien, le nombre de sommets impairs est forcément $0$ ou $2$.

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 $3$, $3$, $3$ et $5$ 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 $2$, $4$, $4$, $4$, $3$ et $3$. 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 $0$ ni $2$.

Le graphe est Eulérien. La définition nous indique 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$.

Regardons un sommet autre que $s_1$ et $s_{m+1}$ dans cette chaîne. Ce même sommet peut éventuellement exister plusieurs fois dans la chaîne. Chaque occurrence d'un tel sommet, disons $s_i$, est entourée d'arêtes $e_{i-1}, s_i, e_i$. Les deux arêtes $e_{i-1}$ et $e_i$ apportent donc une contribution de $2$ au degré de $s_i$. Le degré de $s_i$ est donc forcément pair.

Pour ce qui concerne $s_1$ et $s_{m+1}$, nous allons distinguer deux cas. Dans le premier cas, $s_1 \not = s_{m+1}$ et dans le deuxième cas $s_1 = s_{m+1}$.

Premier cas ( $s_1 \not = s_{m+1}$) : la contribution de $e_1$ au degré de $s_1$ est de $1$ et celle de $e_m$ au degré de $s_{m+1}$ est aussi de $1$. Les degrés de $s_1$ et $s_{n+1}$ sont donc forcément impairs. Il existe par conséquent exactement deux sommets impairs.

Deuxième cas ($s_1 = s_{m+1}$) : La contribution de $e_1$ au degré de $s_1$ est $1$ et celle de $e_m$ au degré de $s_{m+1} = s_1$ est aussi de $1$. La contribution totale au degré de $s_1$ est donc $2$. Le degré de $s_1$ 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.


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