Prove every strongly connected tournament has a cycle of length $k$ for $k = 3, 4, … n$ where $n$ is the number of vertices.
I know that I need to prove this thm by induction but I am not sure how.
[Math] Prove every strongly connected tournament has a cycle of length k for k = 3, 4, … n where n is the number of vertices.
graph theory
Related Solutions
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.
The base case holds. Take a king in the tournament. Because the graph is strongly connected, $|N^+(v)|,|N^-(v)| \neq \emptyset$. Therefore, both $|N^+(v)|$ and $|N^-(v)|$ have kings. Let the king of $|N^+(v)|$ be $k_+$. Clearly, it has to reach $v$ with a path of length $2$. Thus, we have a cycle of length three.
Now suppose that $G$ has a cycle $C$ of length $c$. There are two cases:
Easy case: There is some $v \in G -C$ s.t. $v$ loses to a $x \in C$ and beats a vertex $y \in C$. Then we splice $v$ into $C$ by $xvy$, creating a cycle of length $c+1$.
Hard case: Suppose that no such $v$ exists. Then we split the vertices of $G - C$ into two disjoint sets: $S$, set of vertices that only lose to vertices in $C$, and $P$, the set of vertices that only beat vertices in $C$. Neither of these sets can be nonempty, or the graph is not strongly connected.
There exists $s \in S$ and $p \in P$ s.t. $s$ beats $p$, otherwise the graph cannot be strongly connected.
Take the vertices $c_1, c_2,c_3 \in C$ s.t. $c_3$ follows $c_2$, which follows $c_1$ in $C$. By definition, $c_1$ beats $s$, $s$ beats $p$, and $p$ beats $c_3$. Splice $s$ and $p$ into $C$ by $c_1spc_3$. By skipping $c_2$, we create a cycle of length $c+1$.
Therefore, we have shown by induction that any strongly connected tournament contains cycles of all lengths $3,...,n$, and thus must contain a Hamiltonian cycle.
For more information, you can check out the paper where this result was first published.
Related Question
- [Math] Prove that every strongly connected digraph has an odd directed cycle if its underlying graph has an odd cycle
- [Math] 2-connected graph has a strongly connected orientation
- [Math] strongly connected graph if and only if every edge belongs simple cycle
- Tournament strongly connected and arc reversal
Best Answer
I suppose you already know that a strongly connected tournament of order $n\gt1$ must contain a $3$-cycle. (If the tournament has no $3$-cycle, it's a transitive tournament, and not strongly connected.) For the induction step you have to show that, given a $k$-cycle (where $3\le k\lt n$), you can construct a $(k+1)$-cycle.
Consider a $k$-cycle $C=\{u_0,\dots,u_{k-1}\}$ with arcs $u_iu_{i+1}$ (addition modulo $k$).
Case I. For some vertex $v\notin C$ there is an arc from $C$ to $v$ and there is also an arc from $v$ to $C$.
Then for some $i\in\{0,\dots,k-1\}$ there are arcs $u_iv$ and $vu_{i+1}$. We get a cycle on the vertex set $C\cup\{v\}$, replacing the arc $u_iu_{i+1}$ with the arcs $u_iv$ and $vu_{i+1}$.
Case II. For each vertex $v\notin C$, either all arcs between $C$ and $v$ are directed from $C$ to $v$, or alse all arcs between $C$ and $v$ are directed from $v$ to $C$.
Let $V$ be the set of all vertices $v$ such that all arcs between $C$ and $v$ are directed from $C$ to $v$, and let $W$ be the set of all vertices $w$ such that all arcs between $C$ and $w$ are directed from $w$ to $C$.
Since the tournament is strongly connected (and $k\lt n$), the sets $V$ and $W$ are nonempty, and there is at least one arc $vw$ with $v\in V$ and $w\in W$. Then $\{u_0,\dots,u_{k-2},v,w\}$ is a $(k+1)$-cycle.