Proof that Transitive Tournament Is Not Strongly Connected

Question

Let T be a transitive tournament with n > 1 vertices.

Prove (by contradiction or otherwise) that T is not strongly connected.

This one has had me stumped for a little while.

As the question suggests proof by contradiction that's my aim but I haven't really progressed.

I can see (from looking at and drawing several examples of transitive tournaments) that there will be a vertex with an in-degree of zero, which would result in there being no way for the graph to be strongly connected, so I feel it's somewhere down this line of thinking, although I doubt that could be used in a proof by contradiction.

Any help or pointing in some direction would be greatly appreciated. Thanks!

Answer 1

Take two vertices $x$ and $y$. Assuming $T$ is strongly connected, there is a directed path from $x$ to $y$. As $T$ is transitive, there is an edge $x\to y$. Inversely, there is a directed path from $y$ to $x$, and therefore an edge from $y\to x$. But now there are two edges connecting $x$ and $y$.

Answer 2

Your observation is correct and you can prove it simply by induction on number of vertices. But even stronger argument holds, in a transitive tournament there is no cycle at all.

(i) First Solution (more elegant): Suppose not, then consider a smallest cycle $C$, this cycle is of size $3$ (Why?*). But if there is 3 vertices $x,y,z$ such that they make a cycle $(x,y,z)$, then there is an edge from $x$ to $y$ and there is an edge from $y$ to $z$ but there is no edge from $x$ to $z$ because we have an edge $z,x$ which contradicts with transitivity.

(ii) Second Solution (Simpler argument): is by induction, first prove that there is an vertex of out-degree zero in transitive tournament, then remove that vertex, you have to show that remaining tournament is transitive. And finally because in each step we remove a vertex which does not participate in any cycle, means that transitive tournament does not contain any cycle.

*(Don't read this part try to prove it yourself) Smallest Cycle in a tournament if exists is of size $3$. Suppose not, then $(x_1,\ldots,x_k)$ are making smallest cycle of size $k>3$. If there is an edge from $x_1$ to any of $x_j, 2<j\le k-1$ then we can make a smaller cycle which contradicts with our assumption so $C$ is not a minimal cycle. As otherwise if for all $x_j, 2<j\le k-1$ there is an edge from $x_j$ to $x_1$ then $x_1,x_2,x_3$ are making a cycle which contradicts with $k > 3$. So if any tournament $T$ has a cycle, $T$ also has a cycle of length $3$

At the end I'd like to propose a homework related to tournaments, Show that every strongly connected tournament is Hamiltonian.

P.S: I know that it's easier to just work with cycles, but I provide this answer in this way to show some simple beautiful stuff about tournaments.