graphe eulérien

théorème d’Euler – graphe –

COMBINATOIRE

Un graphe non-orienté est dit eulérien si on peut le parcourir en partant d’un sommet quelconque et en parcourant chaque arête une fois et une seule pour revenir au sommet de départ. On dit qu’il admet un cycle eulérien. De façon plus visuelle, cela correspond à un graphe que l’on peut dessiner sans lever le crayon.

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.