Retour à la table des matières

Département de mathématiques de l'Université de La Rochelle

 

Chapitre 2 - Graphes hamiltoniens

 

Les théorèmes de Ore et de Dirac

Cette leçon sera beaucoup plus courte que la précédente. Nous y donnerons deux théorèmes concernant les graphes hamiltoniens.

Définition - On dit que le graphe G est hamiltonien s'il possède un lacet de Jordan contenant tous les sommets une fois et une seule. On dit qu'il est semi-hamiltonien s'il possède un chemin de Jordan contenant tous les sommets une fois et une seule.

Exemple -  Les trois graphes ci-dessous sont respectivement non hamiltonien, semi-hamiltonien et hamiltonien.

Contrairement au cas des graphes eulériens, on n'a encore trouvé aucune condition nécessaire et suffisante assurant qu'un graphe est hamiltonien ou semi-hamiltonien. Il existe, cependant, de nombreux théorèmes donnant des conditions suffisantes. Nous en démontrons ici un, dû à O. Ore, et en déduisons comme corollaire un résultat historiquement démontré plus tôt par Dirac.

Théorème - (Ore) Soit G un graphe simple possédant n sommets (n 3). Supposons que, pour tout couple (v,w) de sommets non adjacents, on ait

(où d désigne le degré - le nombre d'arêtes issues du point). Alors G est hamiltonien.

Rappelons qu'un graphe simple est un graphe ne contenant pas de boucle dans lequel deux sommets sont reliés par au plus une arête.

Démonstration - Raisonnons par l'absurde en supposant qu'un graphe G à n sommets satisfait l'hypothèse de l'énoncé mais n'est pas hamiltonien. Quitte à rajouter à G d'autres arêtes, on peut supposer que G est ''non hamiltonien maximal'', id est que le rajout d'une seule arête suffirait à le rendre hamiltonien (remarquons que le rajout d'éventuelles arêtes augmente d(v)+d(w) de sorte que le nouveau graphe continue à satisfaire l'hypothèse sur les degrés). Soit vw l'arête qu'il suffirait de rajouter pour rendre G hamiltonien.

Désignons v par v1 et w par vn. Introduisant cette hypothétique arête (vnv1), on obtient donc un lacet de Jordan

passant une fois et une seule par chaque sommet de G. Il en résulte que

est un chemin de Jordan ``vraiment'' contenu dans G, et donc que G est semi-hamiltonien.

Nous allons établir la contradiction en prouvant que G, non hamiltonien par hypothèse, contient pourtant un lacet de Jordan hamiltonien.

Pour cela, montrons qu'existent, le long du chemin v1 v2 vn, deux sommets consécutifs vi -1 et vi tels que vi soit relié à v1 et vi -1 à vn. Car alors, le circuit dessiné ci-dessous est bien un lacet de Jordan hamiltonien de G d'où la contradiction.

Par hypothèse, v1 et vn ne sont pas adjacents, sinon G serait déjà hamiltonien. Il en résulte que d(v1) + d(vn) n. Supposons que n'existe aucun couple (vi-1,vi) satisfaisant la propriété ci-dessus, et soit vi1, , vik les sommets adjacents à vn. Remarquons que i1 2 et ik n -1. Aucun des sommets v1, vi1+1, , vik+1 ne peut alors être adjacent à v1. Il en résulte que

soit

qui contredit l'hypothèse. Ceci termine la démonstration.

Corollaire - (Dirac) Si G est un graphe simple à n sommets et si, pour tout sommet v, d(v) n/2, G est hamiltonien.