2
$\begingroup$

A tournament is a directed graph where between any two distinct vertices there is either the edge (u,v) or the edge (v,u) (one of them only). I have not come across a proper explanation on why the statement is true. However my idea is that it is true because chords form shorter cycles and this eventually leads to a triangle. I am not entirely sure on how this can be shown. I would really appreciate if you guys can give me some hints. Thanks in advance.

$\endgroup$
1
  • $\begingroup$ Your idea is correct. Take any cycle, and then look at any of its diagonals. $\endgroup$ Feb 19 at 15:37

2 Answers 2

4
$\begingroup$

The forward direction is trivial. For the reverse, the proof is essentially what you are proposing. You can make your argument rigorous as follows:

Suppose, for the sake of contradiction, that there exists a cyclic triangle-free tournament $G$. Out of all the cycles of $G$, pick one that has the fewest number of vertices and call it $C$. Let $\{v_1, \dots, v_k\}$ be the vertices in $C$ with edges $v_1 \to v_2 \to v_3 \to \dots \to v_k \to v_1$. Now since $G$ is triangle-free we must have $k \geq 4$. Take the pair of vertices $(v_1, v_3)$. Since $G$ is a tournament, either one of the edges $v_1 \to v_3$, $v_3 \to v_1$ is present in $G$. In any case, we have a contradiction (either a shorter cycle $v_1 \to v_3 \to \dots \to v_k \to v_1$ or a triangle $v_1 \to v_2 \to v_3 \to v_1$). Therefore $G$ is acyclic.

$\endgroup$
0
$\begingroup$

You can formulate the same reasoning in a slightly different way. Prove that if a tournament has a cycle then it has a triangle (we call a cycle/triangle in a strong sense, respecting edge directions).

Let there be a cycle. If it is not a triangle then it has an edge joining two its non-adjacent vertices. This edge “breaks” the cycle into two subgraphs. Depending on this edge direction exactly one of this subgraphs is a cycle. And it’s strictly smaller than the previous one. Repeating this reasoning we will inevitably arrive to a triangle.

$\endgroup$

You must log in to answer this question.

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