1
$\begingroup$

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 ? (note: $n$ is the total number of vertices.)

  • 1
    The graphs you are considering are called tournaments: http://en.wikipedia.org/wiki/Tournament_(graph_theory)2012-03-01

2 Answers 2

2

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
0

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.

  • 0
    Yes, 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