Théorème de Grinberg

En théorie des graphes, le théorème de Grinberg énonce une condition nécessaire pour qu'un graphe planaire possède un cycle hamiltonien, basée sur les longueurs des cycles de ses faces. Le résultat a été utilisé pour construire des graphes planaires non hamiltoniens avec d'autres propriétés, et pour donner de nouveaux contre-exemples à la conjecture de Tait (elle-même réfutée par W. T. Tutte en 1946). Le théorème a été prouvé par mathématicien letton Emanuel Grinberg en 1968.

Un graphe dont on peut démontrer qu'il n'est pas hamiltonien à l'aide du théorème de Grinberg.

Énoncé

Théorème de Grinberg — Soit G un graphe planaire fini possédant un cycle hamiltonien C, plongé dans le plan. Soient $f_{k}$ et $g_{k}$ le nombre de faces à k côtés du plongement qui sont respectivement à l'intérieur et à l'extérieur de C . Alors on a :

$\sum _{k\geq 3}(k-2)(f_{k}-g_{k})=0.$

La démonstration est une conséquence de la formule d'Euler.

Corollaire — Si toutes les faces d'un graphe planaire plongé dans le plan ont un contour de longueur égale à 2 modulo 3, à l'exception d'une seule, alors le graphe n'est pas hamiltonien.

En effet, le facteur $k-2$ dans les contributions des faces dans la formule prise modulo 3 fait qu'elles sont nulles sauf pour la face exceptionnelle unique. Par exemple, pour le graphe de la figure, toutes les faces bornées ont 5 ou 8 côtés, mais la face extérieure a 9 côtés, elle satisfait donc cette condition et le graphe n'est pas hamiltonien. Dans l'exemple donné plus haut, le graphe a avec 46 sommets et 25 faces ; toutes les faces finies ont cinq ou huit arêtes, qui sont toutes deux des nombres qui sont 2 mod 3, et la face infinie a neuf arêtes, qui n'est pas égal à 2 mod 3. Par conséquent, par le corollaire du théorème de Grinberg, le graphe ne peut pas être hamiltonien.

Applications

Grinberg a utilisé le théorème pour trouver des graphes polyédriques cubiques non hamiltoniens avec une connectivité d'arête cyclique élevée. La connectivité d'arête cyclique d'un graphe est par définition le plus petit nombre d'arêtes dont la suppression donne un sous-graphe qui a plus d'une composante cyclique. Le graphe de graphe de Tutte à 46 sommets et les plus petits graphes polyédriques cubiques non hamiltoniens qui en sont dérivés ont tous une connectivité d'arête cyclique égale à trois. Grinberg a utilisé son théorème pour trouver un graphe polyédrique cubique non hamiltonien avec 44 sommets, 24 faces et une connectivité d'arête cyclique égale à quatre, et un autre exemple (celui donné dans la figure) avec 46 sommets, 25 faces et une connectivité d'arête cyclique égale à cinq ; c'est la plus grande connectivité d'arête cyclique possible pour un graphe planaire cubique autre que K₄.

Le théorème de Grinberg a également été utilisé pour trouver des graphes hypohamiltoniens planaires : ce sont des graphes qui ne sont pas hamiltoniens mais qui peuvent être rendus hamiltoniens en supprimant un seul sommet. La construction fait à nouveau usage de ce que toutes les faces sauf une ont un nombre d'arêtes congruent à 2 mod 3. Thomassen (1981) utilise le théorème d'une manière un peu plus compliquée pour trouver un graphe hypohamiltonien cubique plan : le graphe qu'il construit comprend une face à 4 arêtes adjacente à quatre faces à 7 arêtes, et toutes les autres faces ont cinq ou huit arêtes. Afin de satisfaire le théorème de Grinberg, un cycle hamiltonien devrait séparer l'une des faces à 4 ou 7 arêtes des quatre autres, ce qui n'est pas possible.

Limitations

Il existe des graphes planaires non hamiltoniens dans lesquels toutes les faces ont cinq ou huit côtés. Pour ces graphes, la formule de Grinberg prise modulo trois est toujours satisfaite par toute partition des faces en deux sous-ensembles, empêchant l'application de son théorème pour prouver la non-hamiltonicité dans ce cas.

Il n'est pas possible d'utiliser le théorème de Grinberg pour trouver des contre-exemples à la conjecture de Barnette selon laquelle tout graphe biparti polyédrique cubique est hamiltonien. Tout graphe polyédrique bipartite cubique a une partition des faces en deux sous-ensembles satisfaisant le théorème de Grinberg, qu'il possède ou non un cycle hamiltonien.

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Grinberg's theorem » (voir la liste des auteurs).

Bibliographie

• (ru) Emanuels Grinberg, « Plane homogeneous graphs of degree three without Hamiltonian circuits », dans Latvian Math. Yearbook 4, Riga, Izdat. “Zinatne”, 1968 (MR 0238732), p. 51–58. Traduction en anglais par Dainis Zeps « 0908.2563 », texte en accès libre, sur arXiv..
• (de) André Krooss, « Die Barnette'sche Vermutung und die Grinberg'sche Formel », Analele Universităţii din Craiova. Seria Matematică-Informatică, vol. 31,‎ 2004, p. 59–65 (MR 2153849).
• Joseph Malkevitch, « Euler's Polyhedral Formula: Part II », Feature Column, American Mathematical Society,‎ janvier 2005 (lire en ligne).
• Carsten Thomassen, « Planar and infinite hypohamiltonian and hypotraceable graphs », Discrete Mathematics, vol. 14, n^o 4,‎ 1976, p. 377–389 (DOI 10.1016/0012-365X(76)90071-6 , MR 0422086).
• Carsten Thomassen, « Planar cubic hypo-Hamiltonian and hypotraceable graphs », Journal of Combinatorial Theory, vol. 30, n^o 1,‎ 1981, p. 36–44 (DOI 10.1016/0095-8956(81)90089-7 , MR 609592).
• Gábor Wiener et Makoto Araya, « The ultimate question », Arxiv,‎ 2009 (arXiv 0904.3012).
• W. T. Tutte, « Chapter 2: Knights Errant », dans Graph theory as I have known it, New York, The Clarendon Press Oxford University Press, coll. « Oxford Lecture Series in Mathematics and its Applications » (n^o 11), 1998 (ISBN 0-19-850251-6, MR 1635397).
• Joseph Zaks, « Non-Hamiltonian non-Grinbergian graphs », Discrete Mathematics, vol. 17, n^o 3,‎ 1977, p. 317–321 (DOI 10.1016/0012-365X(77)90165-0 , MR 0460189).

Liens externes

• (en) Eric W. Weisstein, « Grinberg Graphs », sur MathWorld