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
does this complete directed graph have this property?
-
1The graphs you are considering are called tournaments: http://en.wikipedia.org/wiki/Tournament_(graph_theory) – 2012-03-01
2 Answers
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.
-
0@Ben, probably because this is a proof by induction, and that's the induction hypothesis. – 2017-11-08
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.
-
0Yes, but we need the path to sta$r$t at the vertex with the most outgoing edges. Does that link answer that? – 2012-03-01