Pour un graphe orienté, un chemin (ou circuit) eulérien passe une et une seule fois par tous les arcs. De même dans le cas non orienté, une chaîne ou cycle eulérien passe une et une seule fois par toutes les arêtes.
Le graphe doit être fortement connexe (ou connexe). En effet, si le graphe ne l’est pas, un ou plusieurs sous-graphes contenant des liaisons ne sont pas atteignables. On constate qu’un cycle ou circuit eulérien contient autant de liaisons arrivant à un sommet qu’il en part (on arrive à un sommet pour en partir)
Conditions nécessaires et suffisantes du circuit/cycle eulérien. Le graphe est connexe (ou fortement connexe). Quel que soit un sommet du graphe, son degré est pair (son degré sortant est égal à son degré entrant).
Puisque tous les sommets possèdent un degré pair, nous savons qu’il existe un circuit. Un parcours est une union de circuits disjoints au niveau des arêtes. Si l’on retire les arêtes d’un parcours alors les degrés sont toujours pairs. Supposons qu’il n’existe pas de parcours donnant un cycle eulérien. Si l’on retire un parcours avec un maximum d’arête au graphe alors les degrés restent pairs. Mais dans ce cas, il existe un circuit disjoint de notre parcours maximum. Le parcours étant une union de circuits disjoints, on en conclut que le parcours initiale n’était pas maximum. En en déduit que le parcours maximum contient toutes les arêtes du graphe. La démonstration est identique pour le cas orienté.
Soit un graphe admettant une chaîne eulérienne. Rajouter une arête entre le début et la fin de la chaîne nous donnera un cycle eulérien. De même, si l’on supprime une arête quelconque d’un cycle eulérien, on aura une chaîne eulérienne.
Avec cette transformation, nous en déduisons les conditions nécessaires et suffisantes pour qu’un graphe possède une chaîne (ou chemin) eulérien.
Conditions nécessaires et suffisantes de la chaîne/chemin eulérien. Le graphe est connexe (ou fortement connexe). Pour tous sommets du graphe, sauf éventuellement deux, son degré est pair (son degré sortant est égal à son degré entrant + ou – 1 pour éventuellement deux sommets.
Problème : graphe hamiltonien
Dans un graphe orienté, un circuit ou un chemin hamiltonien est un circuit ou chemin passant une et une seule fois par tous les sommets. De même pour le cas non orienté.
Il n’existe pas à ce jour de conditions nécessaires et suffisantes mais seulement des conditions suffisantes portant sur les degrés des sommets.
Dirac 1952. Un graphe simple à n sommets (n>2) dont chaque sommet a un degré au moins égale à n/2 est hamiltonien.
Ore 1960. Un graphe simple à n sommets (n>2) tel que la somme des degrés de toute paire de sommets non adjacents vaut au moins n est hamiltonien.
Posa 1962. Un graphe simple à n sommets (n>2) tel que pour tout k, 0<k<(n-1)/2 le nombre de sommets de degré inférieur ou égal à k est inférieur à k. Le nombre de sommets de degré inférieur ou égale à (n-1)/2 est inférieur ou égal à (n-1)/2.
