I have a theorem about Hamiltonian paths in graph, but I doubt it's possible.

Theorem If vertex $v$ of graph $G$ is not isolated, and degree of every other vertex is $\geq k$ for $k \geq 2$, and $|V| \leq 2k-1$, then $v$ is connected by hamiltonian paths with every vertex in $G$.

Proof: Let $G'=G-v$. $|G'| \leq 2k-2$, and for every two vertices of $G': deg(x)+deg(y) \geq 2k-2$. It can be shown from one of the theorems, that $G'$ is hamiltonian. Now, if we join vertex $v$ to the $G'$, it'll be connected with vertices on the hamiltonian cycle, and degree of every its vertex is $\geq k$. How can I, in this point, prove that $v$ is connected with every vertex of cycle by hamiltonian path?

Do you know any theorems that state about existance of various hamiltonian paths in graph, between one vertex and another set of vertices?

And do I clearly understand, that above theorem doesn't work for let's say cycle, connected with $v$ by only one edge? You cannot construct hamiltonian path between $v$ and the first vertex, to what it's connected. (In the picture: A is not connected to B by a hamiltonian path)

So, is it possible to fix the statement of this theorem, so it is true?

Thank you for any help. I'd appreciate all ideas.

  • $\begingroup$ This theorem is from article: "On maximal paths and circuits of graphs" - Erdos, Gallai $\endgroup$ – Olga Feb 1 at 6:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.