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)$
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:
C in $G$, and a vertex $x$ outside of $C$">
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:
x">
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:
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.)
J. W. Moon, On $k$-cyclic and pancyclic arcs in strong tournaments. J. Combin. Inform. System Sci. 19 (1994), no. 3-4, 207–214.