Strongly connected directed clique, Hamiltonian cycle 
Let $G$ be a directed clique. Prove that $$G \text{ has Hamiltonian cycle} \Leftrightarrow G\text{ is strongly connected}$$

$(\Rightarrow)$ is obvious, but I completely don't know how to prove $(\Leftarrow)$
 A: I'm assuming "directed clique" means "tournament".

Theorem: Let $G$ be a tournament.  If $G$ is strongly connected then $G$ has a Hamilton cycle.

As with many Hamilton cycle proofs, we assume the longest cycle is $C$ and there is a vertex $x$ outside of $C$, then construct a larger cycle, giving a contradiction.  The situation looks like this:

Let $v_0,v_1,\ldots,v_{n-1}$ be the vertices of $C$, labelled in order.
Situation 1: $v_i x$ and $x v_{i+1 \mod n}$ are both edges in $G$, for some $i \in \{0,1,\ldots,n-1\}$.  Then we can find a longer cycle as depicted below, giving a contradiction.

Situation 2: $v_i x$ and $x v_j$ are both edges in $G$, for some $i,j \in \{0,1,\ldots,n-1\}$.  Claim: there exists some $k \in \{0,1,\ldots,n-1\}$, such that $v_k x$ and $x v_{k+1 \mod n}$ are both edges in $G$.  Hence we are in Situation 1, and we can extend the cycle, giving a contradiction.
Cute proof of the claim:  For $i \in \{0,1,\ldots,n-1\}$, colour vertex $v_i$ black if $v_i x$ is an edge in $G$, or white if $x v_i$ is an edge in $G$.  (Exactly one of these edges are present for each $i \in \{0,1,\ldots,n-1\}$ since $G$ is a tournament.)  An example is illustrated below:

Hence $C$ forms a necklace, and we know there is at least one white bead, and one black bead.  So there is must be at least one black bead followed by one white bead.
Situation 3: There are two vertices $x$ and $y$ outside of $C$ for which (a) there is a path from $x$ to $y$ contained outside of $C$, (b) $v_i x$ is an edge in $G$ for some $i \in \{0,1,\ldots,n-1\}$ and (c) $y v_j$ is an edge in $G$ for some $j \in \{0,1,\ldots,n-1\}$.
First, we observe that $v_i x$ is an edge in $G$ for all $i \in \{0,1,\ldots,n-1\}$, otherwise we are in Situation $2$ for $x$.  Similarly, $y v_j$ is an edge in $G$ for all $j \in \{0,1,\ldots,n-1\}$.
We can find a longer cycle as depicted below, giving a contradiction.

Finally, we observe that Situation 3 (or Situation 1) is unavoidable.  We simply take a non-self-intersecting walk starting at a vertex in $C$ to a vertex outside of $C$, then walk back to some vertex in $C$.  Such a walk exists, since $G$ is strongly connected.  The first vertex we visit outside of $C$ we call $x$, and the last vertex we visit outside of $C$ we call $y$.
This completes the proof.  Some remarks:


*

*Various papers assert this was first proved in the paper:



P. Camion, Chemins et circuits hamiltoniens des graphes complets.  C. R. Acad. Sci. Paris 249 (1959) 2151–2152. (In French)

(I don't have access to this paper, and doubt I would understand it even if I did have access.)


*

*One strengthening of this result is by Moon who showed that there are at least $3$ directed edges belonging to directed cycles of all possible lengths ($3,4,\ldots,n$ where $n$ is the number of vertices in $G$):



J. W. Moon, On $k$-cyclic and pancyclic arcs in strong tournaments. J. Combin. Inform. System Sci. 19 (1994), no. 3-4, 207–214.

