Le graphe eulérien est-il nécessairement connecté?
Si un graphe est eulérien (c'est-à-dire qu'il a un tour eulérien), alors supposons-nous immédiatement qu'il est connecté?
La raison pour laquelle je pose la question est que je suis tombé sur cette question:
Graphique et son graphique linéaire contenant tous deux des circuits eulériens
Et la solution semble supposer que le graphe est connecté, avant d'utiliser le résultat qu'un graphe connexe est eulérien si et seulement si chaque sommet a un degré pair.
Réponses
Un graphique $G$ avec un circuit d'Euler n'a pas besoin d'être connecté, mais le sous-graphe induit par les sommets qui sont sur le circuit d'Euler doit être un composant connecté de $G$, et tous les autres composants doivent être des sommets isolés. Dans la question à laquelle vous vous êtes lié, il importe peu que$G$ est connecté: même s'il a des sommets isolés, son graphe linéaire sera entièrement dérivé du composant avec le circuit d'Euler et sera donc connecté.
On nous donne que le graphe original a un circuit eulérien. Ainsi, chaque arête doit être connectée l'une à l'autre, que le graphe lui-même soit connecté ou non. Ainsi, le graphique linéaire doit être connecté. Techniquement, cela aurait dû être souligné dans le message de réponse que vous avez lié, oui.