Show that if $G$ is a graph with $|G| \geq 5$ such that for each pair of vertices $u,v$ there is an $u−v$ Hamilton path in $G$, then $\kappa(G) \geq 3$

I do not really have any idea how to start this task. Advices would be appreciated. Thanks.


Hmm, suppose there are $u,v$ such that $G\setminus \{u,v\} $ is disconnected. But there is a path $u-v$ through all the vertices of $G$ on it. So if we remove $u,v$ all the vertices are on the remainder of this path and there for connected. Have I missed something?

  • $\begingroup$ Do we have to require $u$ and $v$ to be adjacent? $\endgroup$ – ensbana Mar 4 at 18:44
  • 1
    $\begingroup$ No, why? $u$ and $v$ are arbitrary @ensbana $\endgroup$ – Maria Mazur Mar 4 at 18:45

Your Answer

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

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