# A tournament is acyclic if and only if it has no triangles

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.

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

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.