Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

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:

The longest cycle $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.

How we can find a longer cycle in Situation 1

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:

Necklace generated by $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.

How we can find a longer cycle in Situation 3

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.