# Proving if (V,A) is a tournament, then (V,A) has a unique complete simple path

I am reading a chapter on tournaments in graph theory and this question came up.

"A tournament is a directed graph obtained by assigning a direction for each edge in an undirected complete graph. That is, it is an orientation of a complete graph, or equivalently a directed graph in which every pair of distinct vertices is connected by a single directed edge."

I know acyclic mean the graph has no cycles. I am having trouble proving the questions below.

show that if $G=(V,A)$ is a tournament, then $G=(V,A)$ has a unique complete simple path if and only is $G=(V,A)$ is acyclic

• This list of conditions equivalent to the two in your question may give you some ideas towards proving the desired result. – Brian M. Scott Jul 30 '16 at 9:06
• @BrianM.Scott I made some edits – Csci319 Jul 30 '16 at 16:39
• If complete simple path means what I think it does, you should be able to prove that uniqueness of this path imposes a strict total ordering on the vertices and therefore is acyclic. The converse could be attacked by showing that without a unique complete simple path, a tournament necessarily contains a cycle. – hardmath Jul 30 '16 at 17:31

## 1 Answer

HINT: Show first that if every vertex has positive out-degree, the digraph must have a cycle. (Just start at any vertex and keep walking from vertex to vertex.) Thus, an acyclic digraph must have a sink (i.e., a vertex with out-degree $0$). Use this to prove by induction on the number of vertices that an acyclic tournament has a unique complete simple path; the induction step is carried out by reducing an acyclic tournament on $n+1$ vertices to one on $n$ vertices by removing the sink. (I say the sink because it’s easy to show that a tournament can have at most one sink.)

For the other direction, suppose that a tournament $T$ has a cycle. Let $C_1$ be a maximal cycle of $T$ of largest possible size. If $T-C_1$ contains a cycle, let $C_2$ be a maximal cycle of maximal size in $T-C_1$. Continue in this fashion to get cycles $C_1,\ldots,C_m$ for some $m\ge 1$ and possibly a final acyclic tournament $T_0$.

• Use the maximality of each $C_k$ in $T-\bigcup_{i<k}C_i$ to show that if $1\le k<\ell\le m$, either every edge of $T$ between $C_k$ and $C_\ell$ is oriented from $C_k$ to $C_\ell$, or every edge of $T$ between $C_k$ and $C_\ell$ is oriented from $C_\ell$ to $C_k$.

Make a new tournament $T'$ that has a vertex $v_k$ for each cycle $C_k$, with an edge from $v_k$ to $v_\ell$ if and only if $T$ has edges from $C_k$ to $C_\ell$.

• Use another maximality argument to show that $T'$ is acyclic and conclude from the first part that $T'$ has a unique complete simple path.
• Use that to show that $T-T_0$ has more than one complete simple path.

If $T_0=\varnothing$, we’re done at this point, so assume now that $T_0\ne\varnothing$.

• Use the first part of the proof to show that $T_0$ has a unique complete simple path with a source $s$.

Let $v_k$ be the last vertex on the complete simple path through $T'$.

• Show that if there is an edge to $s$ from at least one vertex in $C_k$, then $T$ has more than one complete simple path.
• Show that if $T$ has no edge from $C_k$ to $s$, then $T$ has no complete simple path.