Appliquer le théorème d’Euler à un graphe
Créez un compte gratuit pour suivre votre avancement et reprendre où vous avez laissé.
Créer un compteMéthode
Pour déterminer si un graphe admet une chaîne ou un cycle eulérien (et le construire) :
- Étape 1 : vérifier que le graphe est connexe. Sinon, il n'admet ni chaîne ni cycle eulérien.
- Étape 2 : calculer le degré de chaque sommet (nombre d'arêtes incidentes, une boucle compte $2$).
Étape 3 : compter le nombre de sommets de degré impair, puis appliquer le théorème d'Euler :
- $0$ sommet impair : il existe un cycle eulérien (donc aussi une chaîne eulérienne).
- $2$ sommets impairs : il existe une chaîne eulérienne reliant ces deux sommets, mais aucun cycle.
- Tout autre nombre : il n'existe ni chaîne ni cycle eulérien.
- Étape 4 (si la conclusion est positive) : construire un parcours explicite « sans lever le crayon ». La chaîne eulérienne doit commencer et finir aux deux sommets de degré impair. Le cycle eulérien peut commencer en n'importe quel sommet.
Cycle eulérien — graphe en forme de papillon
On considère le graphe ci-dessous (deux triangles partageant le sommet $M$).
Étape 1 : Le graphe est connexe (on passe de tout sommet à tout autre par une chaîne).
Étape 2 : Les degrés des sommets sont :
- $\deg(A) = 2$, $\deg(B) = 2$
- $\deg(M) = 4$
- $\deg(C) = 2$, $\deg(D) = 2$
Étape 3 : Aucun sommet n'est de degré impair. D'après le théorème d'Euler, le graphe admet un cycle eulérien.
Étape 4 : On construit un cycle en utilisant chaque arête une fois et une seule, par exemple :
Ce cycle a $6$ arêtes, ce qui correspond bien au nombre total d'arêtes du graphe.
Chaîne eulérienne — quadrilatère avec une diagonale
On considère le graphe ci-dessous (carré $ABCD$ avec la diagonale $AC$).
Étape 1 : Le graphe est connexe.
Étape 2 : Les degrés sont :
- $\deg(A) = 3$ (relié à $B$, $C$, $D$)
- $\deg(B) = 2$ (relié à $A$, $C$)
- $\deg(C) = 3$ (relié à $B$, $D$, $A$)
- $\deg(D) = 2$ (relié à $C$, $A$)
Étape 3 : Il y a exactement $2$ sommets de degré impair : $A$ et $C$. Le graphe admet une chaîne eulérienne, qui doit nécessairement commencer en $A$ et finir en $C$ (ou inversement). Il n'admet pas de cycle eulérien.
Étape 4 : On construit une chaîne eulérienne partant de $A$ et arrivant à $C$, par exemple :
Cette chaîne utilise les $5$ arêtes du graphe une fois et une seule.
Remarque
Astuce mnémotechnique : un graphe peut être tracé « sans lever le crayon » si et seulement s'il a $0$ ou $2$ sommets de degré impair. C'est l'origine historique du théorème (problème des sept ponts de Königsberg, résolu par Euler en 1736).
Attention
Avant de chercher la chaîne eulérienne, vérifier la connexité : un graphe non connexe ne peut jamais être parcouru en suivant ses arêtes (impossible de sauter d'un morceau à l'autre).
L'erreur classique consiste à conclure trop vite à l'existence d'une chaîne eulérienne dès qu'il y a peu de sommets de degré impair, sans vérifier la connexité.