0
$\begingroup$

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

Thank you for your help.

$\endgroup$
3
  • $\begingroup$ What are your thoughts on that? $\endgroup$
    – mucciolo
    Nov 9, 2017 at 23:22
  • $\begingroup$ 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. $\endgroup$
    – bof
    Nov 9, 2017 at 23:57
  • $\begingroup$ 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. $\endgroup$
    – bof
    Nov 9, 2017 at 23:58

1 Answer 1

Reset to default
1
$\begingroup$

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?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .