MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 or "Traceability of k-traceable oriented graphs" at

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