0
$\begingroup$

I want to present you a lemma, that I've almost proved, but i'm stuck at the very end of it.

Lemma If vertex $v$ of a graph $G$ is not isolated and degree of every vertex except $v$ is $\geq k$ (for $k \geq 2$), and if $|V(G)| \leq 2k-1$, then $v$ is connected by hamiltonian paths with every vertex from $G$.

Proof: Let $G'$ be graph $G-v$. $V(G') \leq 2k-2$ , and for any two vertices in $G'$: $deg(x)+deg(y) \geq 2k-2$. It can be proved from the theorem that $G'$ is hamiltonian (it's not the point of issue). Now let us connect to graph $G'$ vertex $v$, it'll be connected with vertices on the hamiltonian cycle, and the degree of every vertex on cycle is $\geq k$.

And now it should be easy to show the main thesis. ($v$ is connected by hamiltonian paths with every vertex from $G$)

Maybe someone of you knows from which theorem or lemma does it result? For now, I can't see it clearly, and it seems very simple.

Thank you in advance for every suggestion.

$\endgroup$

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.