Coloriages de graphe et tournois

Énoncé du problème

Un tournoi sur $n$ joueurs est un graphe orienté complet : pour chaque paire $\{i, j\}$, soit $i \to j$ (i bat j), soit $j \to i$.

Montrer que tout tournoi possède un chemin hamiltonien (un chemin passant par tous les sommets).
Un tournoi est dit transitif si $i \to j$ et $j \to k$ implique $i \to k$. Montrer qu'un tournoi est transitif si et seulement si son chemin hamiltonien est unique.
Compter le nombre de tournois transitifs sur $n$ joueurs.

Existence d'un chemin hamiltonien :
Par récurrence sur $n$. Pour $n = 2$ : trivial.
Pour $n ge 3$ : soit $P = v_1 \to v_2 \to \cdots \to v_{n-1}$ un chemin hamiltonien sur $n-1$ sommets (par HR).
Soit $v_n$ le $n$-ième sommet. Si $v_n \to v_1$, on insère $v_n$ en tête. Si $v_{n-1} \to v_n$, en queue.
Sinon, il existe $i$ tel que $v_i \to v_n$ et $v_n \to v_{i+1}$ : on insère $v_n$ entre $v_i$ et $v_{i+1}$.
Tournoi transitif $\Leftrightarrow$ chemin hamiltonien unique :
Si transitif : l'ordre donné par le chemin hamiltonien est un ordre total, donc unique.
Si non-transitif : il existe un cycle $i \to j \to k \to i$, ce qui permet de permuter ces trois sommets pour obtenir un deuxième chemin hamiltonien.
Nombre de tournois transitifs :
Un tournoi transitif est entièrement déterminé par l'ordre linéaire de ses sommets (le rang dans le chemin hamiltonien). Il y a donc exactement $n!$ tournois transitifs sur $n$ sommets numérotés.
Si les sommets ne sont pas distingués, il n'y en a qu'un seul à isomorphisme près.

Énoncé du problème