# 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)$

-

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.

-