Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

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.

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.

share|improve this question
One way to try and solve this problem is to list all the properties a counter-example would have, and try to see if there are some contradiction. So, suppose $G$ is a non-traceable $k$-traceable $d$-regular oriented graph of order $2k$, then $G$ has the following properties: 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. –  Alewyn Burger Oct 3 '12 at 10:13
It is amazing to think there are 2k choose k ways to split the graph, and for EACH of those splits, both halves have a Hamilton path. How can the whole graph NOT have a Hamilton path? –  Alewyn Burger Oct 5 '12 at 7:30

Your Answer


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

Browse other questions tagged or ask your own question.