Exercice 9, § 2

Soit $(W,S)$ un système de Coxeter (LIE, IV, §1, p. 11, déf. 3) ; on suppose que le groupe W est fini.

a) On suppose que $(W,S)$ est irréductible et a au plus deux sommets. Démontrer que le graphe de Cayley $\mathscr{G}(W,S)$ est hamiltonien.

b) On suppose que $(W,S)$ est irréductible et a au moins trois sommets. Soit $s\in S$ un sommet terminal (LIE IV, annexe) du graphe de Coxeter associé à $(W,S)$. On pose $S'= S-\{s\}$ et on note $W'$ le sous-groupe de W engendré par $S'$. Soit Γ le graphe dont l’ensemble des sommets est l’ensemble des classes à gauche modulo $W'$ dans W et tel que deux sommets distincts A et B sont reliés par une arête exactement si et seulement si $As\cap B$ n’est pas vide. À l’aide d’un sous-arbre maximal du graphe Γ, démontrer que si le graphe de Cayley $\mathscr{G}(W',S')$ est hamiltonien, il en est de même du graphe $\mathscr{G}(W,S)$.

c) Démontrer que le graphe de Cayley $\mathscr{G}(W,S)$ est hamiltonien (théorème de Conway–Sloane–Wilks).