Exercice 8, § 2

On dit qu’un lacet $(a_0, f_1, . . . , f_n, a_n)$ dans un graphe G est hamiltonien si pour tout sommet $s$ de G, il existe un unique entier $m\in \{1, . . . , n\}$ tel que $a_m=s$. On dit qu’un graphe est hamiltonien s’il existe un lacet hamiltonien dans G.

a) Soit S un ensemble fini de cardinal $\geqslant 3$ et soit $K_S$ un graphe complet d’ensemble de sommets S. Démontrer que le graphe $K_S$ est hamiltonien. Plus précisément, démontrer que pour toute orientation A de G, il existe un lacet hamiltonien dans $K_S$ dont toute flèche appartient à A.

b) On note $\mathscr{G}_S$ l’ensemble des sous-graphes de $K_S$ dont l’ensemble des sommets est égal à S. Soit $\preccurlyeq$ la relation d’ordre la moins fine dans l’ensemble $\mathscr{G}_S$ pour laquelle $G\preccurlyeq G'$ s’il existe des éléments $u, v$ de S tels que deg($u$) $+$ deg($v$)$\geqslant$ Card(S) et tels que Fl(G$'$) soit la réunion de Fl(G) et des deux flèches de $K_S$ d’extrémités $u$ et $v$.

Démontrer que, pour tout $G\in \mathscr{G}_S$, l’ensemble des éléments H de $\mathscr{G}_S$ tels que $G\preccurlyeq H$ possède un unique élément maximal ; on le note $c(G)$.

c) Soit G un sous-graphe de $K_S$ d’ensemble de sommets S. Démontrer que le graphe G est hamiltonien si et seulement s’il en est de même du graphe $c(G)$. d) Soit G un sous-graphe de $K_S$ dont l’ensemble des sommets est S et dont le degré en chaque sommet est $\geqslant$ Card(S)$/2$. Démontrer que $c(G)$ est égal à $K_S$. En déduire que G est un graphe hamiltonien (théorème de G. Dirac).