# does this complete directed graph have this property?

Suppose $G$ is a graph such that every pairs of vertex $u,v$ has either direct edge from $(u,v)$ or $(v,u)$ but not both. For this graph if I start from the vertex $v_1$ with the most out going edge, can I find a path that traverse all vertices, such that $v_1,...v_n$ is the path and $(v_i,v_{i+1})$ for $1 \leq i <n$ ? (note: $n$ is the total number of vertices.)

-
The graphs you are considering are called tournaments: en.wikipedia.org/wiki/Tournament_(graph_theory) – Oliver Mar 1 '12 at 22:00

Let $v_1$ be a vertex with the highest outdegree.

Let $W=\{{w:(w,v_1)\}}$ be the set of vertices with edges directed toward $v_1$. $W$ may be empty, but that's OK.

The vertices in $W$ can be ordered $w_1,w_2,\dots,w_m$ so that $(w_i,w_{i+1})$ is in $G$.

Now grow this ordering of $W$ into an ordering for the vertices other than $v_1$ by the usual method: given an ordering $x_1,x_2,\dots,x_r$ and a new vertex $v$, if $k$ exists such that $(x_i,v)$ is in $G$ for $1\le i\le k$ and $(v,x_{k+1})$ is in $G$ then stick $v$ between $x_k$ and $x_{k+1}$; if no such $k$ exists, then either $(x_i,v)$ is in $G$ for all $i$, in which case you can stick $v$ at the end, or else $(v,x_1)$ is in $G$, and you can stick $v$ at the beginning.

Now this last case must occur at some point, otherwise $(w_1,y)$ is in $G$ for every vertex $y$ with the possible exception of one or more of $\{{w_2,w_3,\dots,w_m\}}$, and then $w_1$ would have outdegree exceeding that of $v_1$.

Therefore, when the ordering of the vertices other than $v_1$ is completed, the first vertex in the list must be one of the vertices not in $W$, that is, one of the vertices $y$ such that $(v_1,y)$ is in $G$. So now you can put $v_1$ at the head of the list, and you are done.

-
So, since your proof shows that it's true, is it possible to do a dfs from $v_1$ to find this path? – Mark Mar 2 '12 at 5:54
I suppose so. It's a finite graph, so any systematic search is going to terminate; since the ordering exists, the search will find it. There may be more efficient ways - I don't know about that. – Gerry Myerson Mar 2 '12 at 6:11

Yes, any Tournament has an odd number of Hamiltonian Paths (proof).

Edit: Sorry, I did misread your problem. From the referenced proof it's not clear whether it is possible to start at the vertex with highest out-degree.

-
Yes, but we need the path to start at the vertex with the most outgoing edges. Does that link answer that? – Aryabhata Mar 1 '12 at 23:52