Exercise 8, § 2

A path $(a_0, f_1, . . . , f_n, a_n)$ in a graph G is said to be hamiltonian if, for every vertex $s$ of G, there exists a unique integer $m\in \{1, . . . , n\}$ such that $a_m=s$. A graph is said to be hamiltonian if there exists a hamiltonian path in G.

a) Let S be a finite set of cardinal $\geqslant 3$ and let $K_S$ be a complete graph whose set of vertices is S. Prove that the graph $K_S$ is hamiltonian. More precisely, prove that for every orientation A of G, there exists a hamiltonian path in $K_S$ every arrow of which belongs to A.

b) Denote by $\mathscr{G}_S$ the set of subgraphs of $K_S$ whose set of vertices is equal to S. Let $\preccurlyeq$ be the least fine order relation in the set $\mathscr{G}_S$ for which $G\preccurlyeq G'$ if there exist elements $u, v$ of S such that deg($u$) $+$ deg($v$)$\geqslant$ Card(S) and such that Fl(G$'$) is the union of Fl(G) and the two arrows of $K_S$ with endpoints $u$ and $v$.

Prove that, for every $G\in \mathscr{G}_S$, the set of elements H of $\mathscr{G}_S$ such that $G\preccurlyeq H$ possesses a unique maximal element; it is denoted by $c(G)$.

c) Let G be a subgraph of $K_S$ whose set of vertices is S. Prove that the graph G is hamiltonian if and only if the graph $c(G)$ is hamiltonian. d) Let G be a subgraph of $K_S$ whose set of vertices is S and whose degree at each vertex is $\geqslant$ Card(S)$/2$. Prove that $c(G)$ is equal to $K_S$. Deduce that G is a hamiltonian graph (theorem of G. Dirac).