En Théorie des graphes, on dit d'un graphe non-orienté qu'il est « eulérien » en référence à Euler (la plupart des mathématiciens écrivent "Eulérien" à cause de l'usage anglo-saxon qui diffère du français, et aussi beaucoup par dandysme) s'il a la propriété suivante :

On peut ordonner les arêtes du graphe de telle façon que deux arêtes consécutives par-rapport à l'ordre (où la dernière et la première arête de l'ordre sont considérées consécutives) sont adjacentes dans le graphe.

Théorème d'Euler

Cette propriété est équivalente au fait que l'on peut « parcourir » le graphe en partant d'un sommet quelconque et en empruntant exactement une fois chaque arête pour revenir au sommet de départ, l'ordre sur les arêtes définissant implicitement le parcours. Déterminer si un graphe est Eulérien ou non est facile grâce au théorème d'Euler (en fait la nécessité de la condition est due à Euler, et sa suffisance à Hierholzer en 1873) :

Théorème d'Euler (1736) - Un graphe connexe est Eulérien si et seulement si chacun de ses sommets est incident à un nombre pair d'arêtes, ou que le nombre de sommets incidents à un nombre impair d'arêtes est égal à 2, c'est-à-dire les points de départ et d'arrivée dans un circuit.

Le graphe de l'enveloppe bien connu est en effet Eulérien: []

La nécessité est pratiquement immédiate (l'argument est le même que pour la résolution du problème des sept ponts de Königsberg). La suffisance n'est pas non plus beaucoup plus dure.

Rappelons d'abord quelques définitions :

• Le degré d'un sommet est le nombre d'arêtes incidentes au sommet ;
• Un parcours est une suite d'arêtes consécutivement adjacentes n'utilisant pas deux fois une même arête et revenant au sommet de départ ;
• Un circuit est un parcours non-vide qui ne repasse pas par un même sommet.

La condition suffisante du théorème d'Euler sus-mentionné s'appuie principalement sur les trois faits suivants :

(1) Si tous les degrés sont pairs et non tous nuls, alors il existe un circuit ;

(2) Un parcours est une union de circuits disjoints - au niveau des arêtes, et non des sommets ;

(3) Si l'on retire les arêtes d'un parcours, alors les degrés pairs restent pairs.

Supposons maintenant que chaque sommet a un degré pair et qu'il n'existe pas de parcours contenant toutes les arêtes. Si l'on considère un parcours avec un nombre maximum d'arêtes et que l'on retire ensuite ses arêtes du graphe, par (3), les degrés restent pairs. D'où, par (1), l'existence d'un circuit disjoint de notre parcours maximum. Mais, par (2), l'union de notre parcours et du circuit forme un autre parcours avec plus d'arêtes, ce qui contredit l'hypothèse de maximalité du parcours initial. Cette contradiction implique donc le théorème.

Application aux graphes orientés

Les résultats ci-dessus s'exportent facilement aux graphes orientés. Un tel graphe est Eulérien s'il a la propriété suivante :

On peut ordonner les arcs du graphe de telle façon que deux arêtes consécutives par rapport à l'ordre - où la dernière et la première arêtes de l'ordre sont considérées comme consécutives - sont consécutives dans le graphe.

Là encore cette propriété signifie que l'on peut « parcourir » le graphe en suivant les arcs depuis leur extrémité initiale vers l'extrémité terminale et en utilisant bien sûr exactement une fois chaque arc et en revenant au point de départ. On montre comme pour la version non-orientée le théorème suivant :

Théorème d'Euler (version orientée) - Un graphe orienté fortement connexe est Eulérien si et seulement si chacun de ses sommets est l'extrémité initiale et terminale du même nombre d'arêtes.

Graphe eulérien et graphe hamiltonien

Finalement, remarquons que le problème de décider si un graphe admet un parcours passant exactement une fois par chaque sommet - c'est-à-dire s'il est un graphe Hamiltonien - est largement plus complexe. C'est un problème NP-complet, avec des applications importantes, qui occupe de nos jours encore de nombreux mathématiciens…

Références

• Reinhard Diestel : Graph Theory. Springer-Verlag Heidelberg, New York, 1997, 2000, 2005. Version électronique de la 3^e édition disponible en ligne gratuitement : document PDF.