# Cycles in non-transitive tournaments

A tournament is a complete, oriented graph. A cycle is directed path that returns to its originating vertex. The length of a cycle is the number of directed edges in the cycle.

(a) Is it true that if a tournament has a cycle of length $k > 3$, it must also have a cycle (or cycles) of length $3$?

(b) What is the proof for (a)?

• What are your thoughts on that? Nov 9, 2017 at 23:22
• It may be easier to think about the contrapositive: Assume that there is no $3$-cycle and prove that there are no cycles at all.
– bof
Nov 9, 2017 at 23:57
• Let's write $x\lt y$ if there is a directed edge from $x$ to $y.$ If there is no $3$-cycle, then the relation $\lt$ is transitive, so it's a total ordering.
– bof
Nov 9, 2017 at 23:58

Hint: Let $G(V,E)$ be a tournament. Given a cycle $C$ of length $k > 3$, denote it by a sequence of vertices $v_1,v_2, \dots ,v_k$ where for all $i$ where $1 \leq i \leq k - 1$, $(v_i, v_{i + 1}) \in E$ and $(v_k,v_1) \in E$.
Now consider the edges between $v_1$ and $v_3$, $v_1$ and $v_4$, $v_1$ and $v_5$, and so on, up until the edge between $v_1$ and $v_{k - 1}$. Since $G$ is a tournament, each of these edges exist, but their directions are unspecified. Is it possible to assign directions to these edges such that there is no 3-cycle among the edges of the cycle and these additional edges?