9
$\begingroup$

If a graph $G$ has at least three vertices, and has a Hamilton Path starting at every vertex, must it contain a Hamilton Circuit?

I have been struggling with this problem. It seems that because every vertex both starts and does not start a Hamilton Path, every vertex is contained in a circuit. But I cannot extend this idea to show that there is a Hamilton Circuit.

$\endgroup$
0

2 Answers 2

10
$\begingroup$

The Petersen graph is a counter example to your problem. All vertices are similar and it is easy to find an hamiltonian path. But there is no hamiltonian cycle in this graph.

I think it is the smallest example but I do not have a proof.

You can easily prove that all vertices must have degree at least 2 (if a vertex has degree 1, then there is no hamiltonian path starting from its unique neighbor).

Hence the smallest counter example has all vertices of degree at least 2. Furthermore, it has no cut vertices (there is no hamiltonian path starting from a cut vertex) and no bridge edge.

$\endgroup$
1
  • 1
    $\begingroup$ The Petersen graph is the smallest HYPOHAMILTONIAN graph (non-hamiltonian, but deleting any vertex leads to a hamiltonian graph), but with this weaker property, there is a smaller graph. Look at the question : Is there a name for graphs with the following property ? $\endgroup$
    – Peter
    Oct 12, 2014 at 19:30
0
$\begingroup$

Hint: try to construct a graph that has a Hamilton path starting at every vertex but which has one vertex of degree one. Such a graph will not have a Hamilton circuit.

EDIT: As Marc van Leeuwen notes below, this is completely bogus. Aline Parreau's counterexample clearly works: as always, when in doubt, try the Petersen graph!

$\endgroup$
2
  • 3
    $\begingroup$ Such graphs do not exist. Starting the purported Hamiltonian path at the unique neighbour of the degree one vertex, one has the choice between going there directly and remaining stuck (since there are at least three vertices), or not going there directly and thus missing the last chance to go there; a contradiction. So this hint does not lead to an answer. $\endgroup$ Sep 24, 2013 at 14:06
  • $\begingroup$ @MarcvanLeeuwen Oops! Quite right. $\endgroup$
    – Erick Wong
    Sep 24, 2013 at 15:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .