↵ pour ouvrir · ↑↓ pour naviguer · Esc pour fermer
Source : Euler, 1736 — premier théorème de théorie des graphes
Un chemin eulérien dans un graphe est un chemin qui passe exactement une fois par chaque arête. Un circuit eulérien est un chemin eulérien fermé (qui revient au point de départ).
1. Dans un circuit eulérien, chaque fois qu'on visite un sommet, on utilise une arête pour y entrer et une pour en sortir → chaque arête contribue 2 au degré du sommet. Donc chaque sommet a un degré pair. ✓
2. Königsberg : 4 sommets de degrés 3, 5, 3, 3 — tous impairs. Pour un circuit eulérien il faudrait tous les degrés pairs. Pour un chemin eulérien il faudrait exactement 0 ou 2 sommets de degré impair. Ici 4 sommets impairs → impossible de traverser chaque pont exactement une fois.
3. Un graphe connexe possède un chemin eulérien (non fermé) si et seulement si il possède exactement 2 sommets de degré impair (le départ et l'arrivée du chemin). Preuve : en ajoutant une arête entre les 2 sommets impairs, on obtient un graphe eulérien (tous degrés pairs) → circuit eulérien → on retire l'arête ajoutée → chemin eulérien. ✓