7
$\begingroup$

Assume $G$ is a tournament, i.e. a (finite) directed graph such that between any two vertices, $a$ and $b$, there is at least one edge in one of the two directions, $a\rightarrow b$ or $b\rightarrow a$.

  1. Show that there is at least one Hamiltonian path, i.e. a path, following the direction of the edges and visiting all vertices exactly once. (This part is a classical exercise and it is here to prepare for the second part of the problem).
  2. Consider all possible losers, i.e. the set of all vertices that can be end-points of Hamiltonian paths of the tournament, see Part (1). Show that the subgraph of all losers has a Hamiltonian cycle, i.e. a cycle that follows the direction of the edges and passes through every vertex exactly once and returns to the initial vertex.

For example

enter image description here

these are all tournaments and the $\color{red}{\text{red}}$ dots are the losers. Notice how there is always a cycle joining them.

$\endgroup$
  • $\begingroup$ Shouldn't the first one with $4$ vertices have only one loser? $\endgroup$ – Vedran Šego Aug 2 '13 at 20:10
  • $\begingroup$ Oh, indeed it should. $\endgroup$ – OR. Aug 2 '13 at 20:11
  • $\begingroup$ For the first statement, check Wikipedia. The proof there is quite nice. $\endgroup$ – Vedran Šego Aug 2 '13 at 20:49
  • $\begingroup$ Yes, I have solved both. I put it here for people's entertainment. $\endgroup$ – OR. Aug 2 '13 at 20:51
  • 3
    $\begingroup$ Solving the problem is not necessarily a waste of time. And it could also be the next guy's question. $\endgroup$ – OR. Aug 2 '13 at 21:03
4
+50
$\begingroup$

This question was mostly answered in my answer to this other question. Instead of typing it all over again, I will quote from that answer. A digraph is strongly connected if there is a (directed) path from every vertex to every other vertex.

Proposition I. A tournament $T$ on $n$ vertices ($n\gt1$) has a Hamiltonian cycle if and only if it is strongly connected.

Proof of the nontrivial direction, quoted from my previous answer:

Suppose $T$ is strongly connected; we have to show that $T$ has a Hamiltonian cycle. We start by showing that $T$ has a cycle, not necessarily of length $n$. Choose a directed edge $uv$. Since $T$ is strongly connected, there is a path from $v$ to $u$; this path, together with the edge $uv$, gives us a cycle in $T$.

Let $C$ be a cycle in $T$ of maximum length $m$; we have to show that $m=n$. Let $W$ (for "winners") be the set of all players that beat at least one player in $C$, i.e., $v\in W$ iff there is a directed edge from $v$ to some vertex in $C$. Similarly, let $L$ (for "losers") be the set of all players beaten by at least one player in $C$, i.e., $v\in L$ iff there is a directed edge to $v$ from some vertex in $C$. We consider several cases.

Case 1. $W=\emptyset=L$.

In this case, the cycle $C$ contains all vertices of $T$; so $m=n$ and everything is fine. We shall see that each of the other cases leads to a contradiction.

Case 2. $W=\emptyset\ne L$.

Then $C$ has no "incoming" edges. If $u\in L$ and $v\in C$, then there is no path from $u$ to $v$, contradicting the assumption that $T$ is strongly connected.

Case 3. $W\ne\emptyset=L$.

If $u\in C$ and $v\in W$, then there is no path from $u$ to $v$, contradicting the assumption that $T$ is strongly connected.

Case 4. $W\cap L\ne\emptyset$.

If $v\in W\cap L$, then we can insert $v$ between two consecutive vertices of $C$ so as to obtain a cycle of length $m+1$, contradicting the assumed maximality of $m$.

Case 5. $W\ne\emptyset$, $L\ne\emptyset$, and $W\cap L=\emptyset$.

Since $T$ is strongly connected, there must be a directed edge $uv$ for some $u\in L$, $v\in W$. Then the vertices $u,v$ can be inserted in the cycle $C$ so as to obtain a cycle of length $m+2$, contradicting the assumed maximality of $m$.

Proposition II. Every tournament has a Hamiltonian path.

The easiest way to prove this is to consider a longest possible path in $T$ and show that, if it does not contain all the vertices, then we can construct a longer path. Another way (Rédei's theorem) is to use the in-and-out principle (aka inclusion-exclusion) to show that the number of Hamiltonian paths in $T$ is an odd number, therefore nonzero. Yet another way is to prove the Gallai-Milgram theorem which has Proposition II as a special case. A very silly way is to derive Proposition II from Proposition I about Hamiltonian cycles, which is what I will do.

Let $T$ be a tournament. It may or may not be strongly connected, but we can embed it in a strongly connected tournament $T'$ by adding two new vertices $u,v$, a directed edge $uv$, and directed edges $tu,vt$ for each $t\in T$. By Proposition I, $T'$ has a Hamiltonian cycle, which clearly has to contain the edge $uv$; deleting the vertices $u,v$ from the Hamiltonian cycle leaves us with a Hamiltonian path in $T$.

Proposition III. The subtournament on the set of all "losers" is strongly connected; hence it has a Hamiltonian cycle, provided there is more than one loser.

[Theorem 2 of my previous answer is essentially equivalent to this, but stated in terms of "winners" rather than "losers".]

Proof. Let $T$ be a tournament. Let $S$ be the set of all vertices $v\in T$ such that, for each vertex $u\in T$, there is a (directed) path from $u$ to $v$. (I will show that $S$ coincides with the set of all "losers" as defined in the question, i.e., the last vertex of some Hamiltonian path; this is just a simpler and more natural way to define them.)

  1. Clearly, every loser belongs to $S$: if there is a Hamiltonian path ending at $v$, then we can get from any vertex to $v$ by following that path.

  2. If $u\in S$ and $uv\in E(T)$ then $v\in S$. This is clear from the definition of $S$.

  3. $S$ is strongly connected. To see this, consider any vertices $u,v\in S$. By the definition of $S$, there is a path from $u$ to $v$ in $T$; since there are no directed edges from $S$ to $T\setminus S$, the whole path must lie in $S$.

  4. We finish the proof by showing that every vertex in $S$ is a loser; i.e., we consider a vertex $v\in S$ and find a Hamiltonian path which ends up at $v$. At any rate, by Proposition II there is a Hamiltonian path in $T$. Since there is no escape from $S$, the path must first traverse all the vertices (if any) in $T\setminus S$, then all the vertices in $S$. If $S=\{v\}$ we're done. Suppose $S$ contains more than one vertex. By Proposition I, we can find a Hamiltonian cycle in $S$; let $w$ be the successor of $v$ on that cycle. Follow the original Hamilton path as long as it stays in $T\setminus S$; then jump to $w$ and follow the cycle around to $v$. Q.E.D.

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