Prove that if a tournament $T$ contains a cycle, then it contains two Hamiltonian paths

Question

Prove that if a tournament $T$ contains a cycle, then it contains two Hamiltonian paths.

How can I prove that, I thought that since $T$ is a tournament it has a Hamiltonian path $P$, and since an induced subgraph of a tournament is a tournament try to use a subgraph $T'$ without $v_0$ one of the vertices that are in the cycle and obtain the path $P'$, finally add the vertex $v_0$ to $P'$ and find the second hamiltonian path, but I'm not sure of my idea, or how it could be by contradiction

Answer 1

Let $T_1,\dots,T_k$ be the strong components (i.e. strongly connected components) of the tournament $T$, where $T_i$ has $n_i$ vertices. A Hamiltonion path in $T$ is determined by choosing a Hamiltonian path in each $T_i$. If each $n_i=1$ then $T$ is a transitive (acyclic) tournament. Since $T$ contains a cycle, we must have $n_i\gt1$ (so $n_i\ge3$) for some $i$. The strongly connected tournament $T_i$ has a Hamiltonian cycle, so it has (at least) $n_i$ Hamiltonian paths, so $T$ has at least $n_i$ Hamiltonian paths.

So the conclusion is that a tournament with a cycle has at least $3$ Hamiltonian paths, but that was expected, since the number of Hamiltonian paths is always odd.

Answer 2

It's true for n≤3. Now take an n-vertex tournament T with n≥4 vertices.

If T contains a vertex x with all out-edges, then we can delete it, use induction to show the remaining graph (which still contains a cycle) has two Hamiltonian paths, both of which can be extended to n-vertex paths by attaching x at the path's endpoint. So now assume every vertex has at least one in-edge.

We first use this proof via strong induction to show T contains a Hamiltonian path, and we order the vertices according to that Hamiltonian path $(v_1,\ldots,v_n)$. We know from the above argument that $v_1$ contains at least one in-edge.

Let $j$ be the maximum index for which there is an edge from $v_j$ to $v_1$. If $j=n$, then we have a Hamiltonian cycle, and we can easily create two Hamiltonian paths from it by deleting edges. Otherwise $3 \leq j < n$, and we have an edge from $v_1$ to $v_{j+1}$ (since we maximized $j$), and we get an additional Hamilton path $(v_2,\ldots,v_j,v_1,v_{j+1},\ldots,v_n)$ as depicted below: