Meyniel's theorem + finding a Hamiltonian path for a specific graph family

Question

Let's say we have a directed graph $G = (V, E)$ for which $(v, w) \in E$ and/or $(w,v) \in E$ holds true for all $v, w \in V$. My feeling is that this graph most definitely is Hamiltonian, and I want to find a Hamiltonian path in it (from any vertex to any other vertex, I don't care where to start or stop).

I wanted to refer to Meylien's theorem for this:

A strongly connected simple directed graph with $n$ vertices is Hamiltonian if the sum of full degrees of every pair of distinct non-adjacent vertices is greater than or equal to 2ドルn − 1.$

There are two subtleties that I'm not sure about with this theorem:

• What is meant by "adjcent vertices". Does the order matter here? Is the pair $(v,w)$ adjacent even if $(w,v) \in E$ but not $(v,w)$ itself? If that is the case and the graph is strongly connected, than it must obviously be Hamiltonian, since there are no non-adjacent pairs of vertices at all.
• A graph with the above property is not necessarily strongly connected. I think this is easy to solve: We can just decompose the graph into SCCs. We will still have no non-adjacent pairs of vertices in the components and all of them are Hamiltonian. We can then construct a Hamiltonian path of the whole graph by connecting them in topological order.

Is the above reasoning correct and the theorem applicable? Or is there some other argument we can use to show that there is a Hamiltonian path in the graph?

In the end I want to actually find the Hamiltonian cycles in the SCCs, but haven't had much luck finding a constructive proof of the theorem, let alone an algorithm that solves this. Can it be done in a straightforward way? I feel like some kind of greedy approach could work, where we take the nodes in decreasing order of outdegree or something similar.

• Yuval Filmus: If exactly one of $(v,w),(w,v)$ is in the graph, then it is known as a tournament.

Answer 1

It is enough to prove your claim for the case of a tournament, in which for every pair of vertices $v\neq w,ドル exactly one of the edges $(v,w),(w,v)$ is in the graph. Wikipedia has an algorithmic proof that every such graph has a Hamiltonian path. If the tournament is strongly connected, it has a Hamiltonian cycle.