Does a strongly connected component necessarily have a Hamiltonian path or cycle?

Question

In a general directed graph, does a strongly connected component necessarily have a Hamiltonian path or cycle? I don't think so, and I've tried to come up with compact counter example, but have yet to come up with one.

Answer 1

We can get a family of counterexamples by joining together many directed $3$-cycles at a single common vertex. For concreteness, say that we have $2n+1$ vertices $\{x, y_1, \dots, y_n, z_1, \dots, z_n\}$ and $3n$ edges: $x \to y_i$, $y_i \to z_i$, and $z_i \to x$ for all $i$.

This is strongly connected: we can follow around the tour $$x \to y_1 \to z_1 \to x \to y_2 \to z_2 \to x \to \dots \to y_n \to z_n \to x$$ to go from any vertex to any other vertex. However:

• For $n\ge 2$, there cannot be a Hamiltonian cycle: to leave vertex $y_1$ and come back, you would need to go through $x$ twice.
• For $n\ge 3$, there cannot even be a Hamiltonian path, for the same reason. The path $y_1 \to z_1 \to x \to y_2 \to z_2$ is Hamiltonian for $n=2$, but for $n\ge 3$, we will not be able to visit three of the $3$-cycles without coming back to $x$.