Graphe eulérien

Terminale ES

Définitions
Soit G un graphe.

Théorème 1
Un graphe connexe G admet un cycle eulérien si et seulement si tous ses sommets sont de degré pair.

Théorème 2
Un graphe connexe G admet une chaîne eulérienne distincte d'un cycle si et seulement si le nombre de sommets de G de degré impair est égal à 2.
Dans ce cas, si A et B sont les deux sommets de G de degré impair, alors le graphe G admet une chaîne eulérienne d'extrémités A et B.

Exemple

Rubriques connexes

Chaîne d'un graphe
Graphe complet
Graphe connexe
Graphe non orienté
Graphe orienté

Pages interactives

181   Cycle eulérien ou chaîne eulérienne d'un graphe simple non orienté Outil
Tale ES