Pourquoi un cycle non orienté ne répète pas d'arête

Trois notions du chapitre s'effondreraient, et une survivrait. C'est cette dissymétrie qui rend la clause intéressante.

Ce qui s'effondre. Avec la seule définition orientée — un chemin fermé de longueur non nulle —, toute arête $\{u,v\}$ donnerait le chemin $u,v,u$, de longueur $2$. Donc :

• aucun graphe possédant une arête ne serait acyclique ;
• la notion d'arbre disparaîtrait : « connexe et acyclique » ne décrirait plus que le graphe à un seul sommet. Mesuré : un arbre à $5$ sommets a $4$ arêtes, donc $4$ allers-retours — quatre « cycles » là où il n'y en a aucun ;
• la notion de forêt disparaîtrait avec elle, ainsi que le dag non orienté et toute la troisième famille remarquable du chapitre.

Ce qui survit. La caractérisation des graphes bipartis — « aucun cycle de longueur impaire » — resterait vraie, parce qu'un aller-retour a pour longueur $2$, qui est paire : les faux cycles introduits ne sont jamais impairs, donc ils ne peuvent disqualifier aucun graphe biparti. La proposition tiendrait telle quelle.

Ce que cette dissymétrie enseigne. Une définition n'est pas neutre : elle est choisie pour que les énoncés qui l'emploient soient vrais et utiles. Ici, la clause « sans répétition d'arête » n'est pas une précaution esthétique — c'est la condition sans laquelle la moitié du vocabulaire du chapitre serait vide. Quand une définition porte une clause qui semble technique, la bonne question est : quel théorème deviendrait faux sans elle ?

Et pourquoi le cas orienté n'en a pas besoin. Parce qu'un aller-retour y demande deux arcs distincts, $u\to v$ et $v\to u$, dont la présence simultanée est déjà une information sur le graphe — c'est un cycle de longueur $2$, et c'en est un vrai. Un graphe orienté acyclique est donc, entre autres, un graphe où l'on ne trouve jamais deux arcs opposés. La définition non orientée doit exclure à la main ce que la définition orientée exclut par construction, puisqu'une arête non orientée est un objet, pas deux.