graph theory
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.
Hint: if $G$ has a Hamilton cycle then for any $S \subset V$ we have that $G-S$ has at most $|S|$ components.
The answer, incidentally, is yes, that such graphs exist. Look for a graph with seven vertices, minimum degree three, that has one vertex that when you remove it yields a graph with more than one component.
Edit: Actually, the line graph on three vertices (o-o-o) works.
Here's the lexicographically first Hamilton cycle (found using a backtracking algorithm):
Best Answer
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.