If each pair of cities has exactly one direct one-way road between them, there is a path which visits each exactly once

Question

Each pair of cities in a nation has exactly one direct one-way road between them. Show that there is a path which visits each city exactly once.

Now, this problem seems ripe for induction, but I have hit a bit of a snag trying to solve it that way. If we assume that this is true for $n$ cities, then I think it would be possible to add a city which only goes to other cities. This city would then not be able to fit onto the path already established, correct? I feel like I'm close, but not quite able to understand how to find a solution yet.

Answer 1

Hint. The problem does not ask you to get back to where you started. So a city such as the one you describe can only be in one place on the tour. . .

Suppose we already have a path from $v_1$ to $v_n$ and the extra city is $u$.

• If $v_1$ has an edge from $u$, place $u$ at the start of the path.
• If $v_n$ has an edge to $u$, place $u$ at the end.
• If neither of these cases apply, go along the path step by step until you find the first vertex with an edge from the extra vertex. (And how do you know there is such a vertex?)

Answer 2

Let's use your inductive hypothesis: Suppose that given a directed graph with $n$ cities, there exists a path passing through each only once. Label the cities so that the path is $$1 \rightarrow 2 \rightarrow \dots \rightarrow n.$$ Now, if your new city has a road leading outwards to city $1$, you can label it city $0$ and append it to the beginning of the path. Likewise, if there is a path inwards from city $n$, label it $n+1$ to complete your path. The difficulty is in showing that in the remaining cases the new city, call it city $t$, can be added to the existing path appropriately: $$ 1 \rightarrow \dots \rightarrow i \rightarrow t \rightarrow i+1 \rightarrow \dots n.$$

This requires showing that there is a pair of consecutive cities, $(i, i+1)$, such that $i$ leads into $t$ and $i+1$ leads out.

Try the following: consider each road from an old city to $t$ in turn; the $(1,t)$ road, the $(2,t)$ road, ... $(n,t)$. (Write an inward road as a right arrow, outward as a left arrow.) Each is directed and if we don't have $1 \leftarrow t$ or $n \rightarrow t$, so we have some sequence of length $n$ such as $$ \rightarrow, \rightarrow, \dots, \leftarrow, \rightarrow, \leftarrow.$$

If we ever come across an inward road followed by an outward road, we have a way to plug $t$ into the sequence. That is, if our sequence ever contains a pair that look like $\dots, \rightarrow, \leftarrow, \dots$ then we have a solution. But we start with a right arrow - if this never happened we must also end with a right arrow, a contradiction.