This problem is a special case of the traceability conjecture for oriented graphs.

For more information on this conjecture see the paper: "Progress on the Traceability Conjecture for Oriented Graphs" at http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/965 or "Traceability of k-traceable oriented graphs" at http://www.sciencedirect.com/science/article/pii/S0012365X09006438.

**Definitions**

A graph is *oriented* if each edge has only one direction. A graph is *traceable* if it contains a Hamiltonian path. A graph is *$k$-traceable* if each of its subgraphs of order $k$ is traceable. An oriented graph is *d-regular* if each vertex has $d$ out-neighbours and $d$ in-neighbours.

**Notes**

Note that for a graph of order $2k$ to be $k$-traceable, we must have $2d \geq k+1 $, otherwise we can select $k$ non-traceable vertices by selecting any vertex $v$ and $k-1$ of its non-neighbours.

It is for example, easy to show that a $k$-traceable $d$-regular graph $G$ of order $2k-1$ is traceable: Select any vertex $v$. Partition the remaining vertices in two sets $I$ and $O$ with $k-1$ vertices each such that $I$ contains only in-neighbours and non-neighbours of $v$, and $O$ contains only out-neighbours and non-neighbours of $v$. Then the subgraph with vertices $I \cup v$ has a Hamilton path ending in $v$, and the subgraph with vertices $O \cup v$ has a Hamilton path starting with $v$, making $G$ traceable.

I am sure there must be a clever trick somewhere to show the special case for order $2k$ is also true.

P1:$G$ is non-traceable.P2:$G$ is $k$-traceable.P3$2d \geq k+1 $. **P4:** $G$ is $(2k-1)$-traceable.P5:$G$ is $(2k-2)$-traceable.P6:For every arc $ab$, there exist a vertex $w$, such that $aw$ and $wb$ are arcs. $\endgroup$ – Alewyn Burger Oct 3 '12 at 10:13