Retour à la table des matières

Département de mathématiques de l'Université de La Rochelle

 

Chapitre 1 - Graphes eulériens

 

B - Caractérisation des graphes eulériens et semi-eulériens

Théorème - Si G est un graphe eulérien, il ne contient aucun point de degré impair ; si G est semi-eulérien, il contient deux points de degré impair.

Démonstration - Supposons que G est eulérien. Dessinons G et effaçons les arêtes que nous avons déjà parcourues. Chaque passage en un point intermédiaire efface deux arêtes (arrivée et départ). Ces points intermédiaires sont donc de degré pair puisqu'à la fin plus aucune arête n'y aboutit. Soit M le point de départ (et aussi d'arrivée) : chaque passage intermédiaire a effacé deux arêtes, le premier en avait effacé une et le dernier en efface une autre. Cela fait au total un nombre pair d'arêtes pour ce point aussi. Lorsque G est semi-eulérien, le même raisonnement montre que le premier et le dernier point du tracé sont exactement les deux seuls points de degré impair.

Remarque -  Le fait que M soit de degré pair (dans le cas eulérien) peut aussi s'obtenir en utilisant le (b) du lemme des poignées de main.

Remarque -  Il résulte notamment du théorème qu'un graphe ne peut pas être simultanément eulérien et semi-eulérien.

Exemple -  le graphe d'Euler et le graphe de l'enveloppe

ne sont ni eulériens ni semi-eulériens. Le rajout, n'importe où, d'une seule arête les rend tous deux semi-eulériens (à condition que cette arête ne soit pas une boucle).

La chose remarquable, en ce qui concerne le théorème, est qu'une condition nécessaire d'une telle simplicité soit également suffisante.

Théorème - Soit G un graphe connexe.

(a) On suppose que G ne contient aucun point de degré impair. Alors G est eulérien.

(b) On suppose que G contient deux points de degré impair. Alors G est semi-eulérien.

L'hypothèse selon laquelle G est connexe est clairement inévitable.

Démonstration - Soit n le nombre d'arêtes du graphe. Nous raisonnons par récurrence sur n.

Si n= 1, il n'y a que deux cas possibles, A1A1 et A1A2 et le résultat est évident (le premier vérifie (a) et il est eulérien, le second vérifie (b) et il est semi-eulérien). Supposons donc le point (a) du théorème vrai pour tous les graphes G' possédant au plus n-1 arêtes. Soit G un graphe possédant n arêtes et dans lequel aucun point n'est de degré impair.

Partons d'un point quelconque de G, soit A0, et traçons à l'aveuglette un chemin de Jordan. Puisque G n'a qu'un nombre fini d'arêtes, ce chemin se termine forcément en un certain point A'. Si A' était différent de A0, il en résulterait, en reprenant l'argument du théorème , que l'on a effacé un nombre impair d'arêtes arrivant en A', et on pourrait donc continuer pour encore au moins une étape le chemin. Donc A' = A0 et notre chemin est donc un lacet de Jordan. Retirons-le du graphe, en l'effaçant. Il reste des sommets et des arêtes, formant plusieurs ''petits graphes'' connexes (numérotés sur la figure de 1 à 4).

Chacun de ces morceaux rencontre notre lacet en au moins un point (c'est dans cette remarque qu'intervient la connexité de G). Pour chacun d'eux, et vu la manière dont on a effacé les arêtes, il n'existe aucun point de degré impair. Par conséquent, chacun de ces petits graphes est eulérien d'après l'hypothèse de récurrence. Si l'on désigne alors par Gi (1 i 4) des lacets de Jordan épuisant les arêtes de chacun d'eux et de point initial et final Mi, le chemin suivant est un lacet de Jordan épuisant toutes les arêtes de G (avec des conventions d'écriture évidentes) : A0M1, G1, M1M2, G2, M2M3, G3, M3M4, G4, M4A0.

Ceci démontre (a).

Le point (b) en résulte. On ne refait pas la récurrence mais on trace cette fois un chemin de Jordan maximal à partir de l'un des deux points de degré impair. Ce chemin se termine forcément sur l'autre point de degré impair. Ayant retiré ce chemin, on reprend la démonstration faite pour le (a) (il faut noter que les petits graphes qui apparaissent sont tous eulériens).