3
$\begingroup$

If a graph $G$ is such that from every vertex $v$ there is a Hamiltonian path, does that imply that there is a Hamiltonian cycle?

I've tried a constructive proof, but to no avail. No other ideas occur to me. I'd rather have just hints :-) No fun otherwise...

$\endgroup$

marked as duplicate by mrp, Community May 6 '17 at 10:48

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Are the graphs directed or undirected? $\endgroup$ – mrp May 6 '17 at 8:25
3
$\begingroup$

Hint. I found a counterexample. It's a very symmetric graph with $10$ vertices, and you've probably seen it before. The symmetry (i.e., vertex-transitivity) makes it really easy to check that there's a Hamilton path from every vertex; you just have to find one Hamilton path.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.