[Math] Transitive tournament

graph theoryhamiltonian-path

1.) Prove that a tournament (i.e., an orientation of $K_n$) is a transitive tournament if and only if it does not have any directed cycles of length $3$.

2.) Prove that a tournament is strongly connected if and only if it has a directed Hamiltonian cycle.

I tried this for Question 2. If $G$ has a directed Hamilton cycle (thus a directed closed walk containing every vertex at least once), then $G$ is strongly connected. The converse that $G$ has direct Hamiltonian cycle assuming that $G$ is strongly connected. Since $G$ is a tournament, then it implies there is an open Hamiltonian path. I do not know where to continue from here.. Can anyone help me prove it? I would appreciate it.

Best Answer

Let's call your tournament $T$, and write $a \rightarrow b$ when there is an arc from $a$ to $b$. Write $a \rightarrow B$ when $B$ is a vertex set and $a$ has an arc to all members of $B$. Finally write $B \rightarrow a$ when all members of a set $B$ have an arc to $a$.

1) is straightforward enough. If $T$ has a cycle of length 3, then it can't be transitive by definition. Conversely, suppose $T$ is not transitive. Then $\forall a,b,c \in V(T) [a \rightarrow b, b \rightarrow c \Rightarrow a \rightarrow c]$ is false. What do you get by negating this expression ?

2) There's probably a better way for the tougher direction, but here goes. One way is to suppose $T$ has no Hamiltonian cycle and get that $T$ is not strongly connected. Let $C = c_1c_2 \ldots c_k c_1$ be a directed cycle of $T$ with the largest number of vertices.

Let $x \in V(T)$ such that $x \notin C$. If $c_i \rightarrow x$ for some $c_i \in C$, then $c_{i + 1} \rightarrow x$ as otherwise, $x \rightarrow c_{i+1}$ and $C' = c_1c_2 \ldots c_i x c_{i + 1} \ldots c_k c_1$ would be a bigger cycle (but $C$ is a largest cycle by assumption). Applying this reasoning inductively, we have that $C \rightarrow x$ when some $c_i \rightarrow x$.

So what do you get for any $x$ outside $C$ ? Either $C \rightarrow x$ or $x \rightarrow C$. Let $X = \{x : C \rightarrow x\}$ and $Y = \{y : y \rightarrow C\}$. Take $x \in X, y \in Y$. If $x \rightarrow y$, then you can extend the $C$ cycle by deviating with $c_ixyc_{i + 1}$. So $y \rightarrow x$, for all $x \in X, y \in Y$. From this, you can deduce that there is no way to go from $x \in X$ to $c_i \in C$, hence $T$ is not strongly connected.

What's left for you to do is to argue that $C$ exists, and handle the cases when $X$ or $Y$ is empty (and tell us why both can't be empty).

Related Question