-1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ This list of conditions equivalent to the two in your question may give you some ideas towards proving the desired result. $\endgroup$ – Brian M. Scott Jul 30 '16 at 9:06
  • $\begingroup$ @BrianM.Scott I made some edits $\endgroup$ – Csci319 Jul 30 '16 at 16:39
  • 1
    $\begingroup$ 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. $\endgroup$ – hardmath Jul 30 '16 at 17:31
1
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.