Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.)

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

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.