Théorème de Fleischner

Un graphe non orienté G est hamiltonien s'il contient un cycle qui passe par chacun de ses sommets exactement une fois. Il est 2-connexe (ou biconnexe) s'il ne possède pas de point d'articulation, un sommet dont la suppression déconnecte le graphe. Tous les graphes biconnexes ne sont pas hamiltoniens : des contre-exemples sont par exemple le graphe de Petersen et le graphe biparti complet K _2,3 .

Le carré de G est un graphe G ² qui a le même ensemble de sommets que G, et dans lequel deux sommets sont adjacents si et seulement s'ils ont une distance d'au plus deux dans G. Le théorème de Fleischner est :

De manière équivalente, les sommets de chaque graphe biconnexe G peuvent être ordonnés cycliquement de telle sorte que les sommets adjacents dans cet ordre soient à une distance d'au plus deux les uns des autres dans G.

Dans le théorème de Fleischner, on peut contraindre le cycle hamiltonien de G ² à ce que pour deux sommets donnés v et w de G il contienne deux arêtes de G incidentes à v et une arête de G incidente à w . De plus, si v et w sont adjacents dans G, alors ce sont trois arêtes différentes de G[1].

En plus d'avoir un cycle hamiltonien, le carré d'un graphe G biconnexe est également connexe au sens hamiltonien (ce qui signifie qu'il possède chemin hamiltonien commençant et se terminant en deux sommets spécifiés) et être 1-hamiltonien (ce qui signifie que si un sommet est supprimé, le graphe restant possède encore un cycle hamiltonien)[2] . Il est également un graphe pancyclique, ce qui signifie que pour chaque sommet v et tout entier k avec ${\displaystyle 3\leq k\leq |V(G)|}$, il existe un cycle de longueur k contenant v[3].

Si un graphe G n'est pas biconnexe, alors son carré peut ou non avoir un cycle hamiltonien, et déterminer s'il en a un est NP-complet[4].

Un graphe infini ne peut pas avoir un cycle hamiltonien, car chaque cycle est fini, mais Carsten Thomassen a prouvé que si G est un graphe biconnexe localement fini avec une seule bout, alors G ² a un chemin hamiltonien doublement infini[5]. Plus généralement, si G est localement fini, biconnex et a un nombre quelconque de bouts, alors G ² a un cercle hamiltonien. Dans un espace topologique compact obtenu en considérant le graphe comme un complexe simplicial et en ajoutant un point supplémentaire à l'infini à chacune de ses bouts, un cercle hamiltonien est défini comme un sous-espace homéomorphe à un cercle euclidien qui couvre chaque sommet.

Le cycle hamiltonien dans carré d'un graphe biconnexe à n sommet peut être trouvé en temps linéaire[6], ce résultat datant de 2018 améliore la première solution algorithmique de Lau en temps d'exécution O (n ² )[7]. Le théorème de Fleischner peut être utilisé pour fournir une 2-approximation du problème de goulot d'étranglement du voyageur de commerce dans les espaces métriques[8].

Une preuve du théorème de Fleischner a été annoncée par Herbert Fleischner en 1971 et publiée par lui en 1974, résolvant ainsi une conjecture de 1966 de Crispin Nash-Williams, énoncée également indépendamment par L. W. Beineke et Michael D. Plummer[9]. Dans son compte-rendu de l'article de Fleischner, Nash-Williams écrit que celui-ci avait résolu « un problème bien connu qui a résisté pendant plusieurs années l'ingéniosité d'autres théoriciens des graphes »[10]

La preuve originale de Fleischner était compliquée. Václav Chvátal, dans l'article où il introduit la ténacité graphique, observe que le carré d'un graphe k-sommet-connexe est nécessairement k-dur; il conjectura que les graphes 2-durs sont hamiltoniens, ce qui aurait donné une autre preuve du théorème de Fleischner[11]. Des contre-exemples à cette conjecture ont été découverts plus tard, [12] mais la possibilité qu'une borne finie sur la dureté pourrait impliquer le caractère hamiltonien reste un problème ouvert important dans la théorie des graphes. Une preuve plus simple, à la fois du théorème de Fleischner et de ses extensions par [13], a été donnée par (Říha 1991)[14], et une autre démonstration simplifiée du théorème a été donnée par Georgakopoulos en 2009[15]'[16]'[17].