How to construct a Hamilton path from a complete directed graph

Question

Given a directed graph.

Any 2 vertices are adjacent. The edge connecting a pair of vertices may be uni-directional or bi-directional.

How do I find a Hamilton path?

Side notes:

• Wikipedia says "A strongly connected simple directed graph with n vertices is Hamiltonian if every vertex has a full degree greater than or equal to n." Therefore, a solution must exist in my problem.
• I understand that the general Hamilton path problem is NP-Complete. But it feels like this specific version should have a polynomial solution.

Answer 1

Use a variant of insertion sort to construct a path in quadratic time. Given a path

v1 v2 ... vn-1

on a subset of vertices, consider how to insert vn. If vn has an arc to v1, then prepend vn. If vn-1 has an arc to vn, then append vn. Otherwise, there exists by Sperner's lemma an index i such that vn has an arc from vi and an arc to vi+1. Insert it there.