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.
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.
Copyright © 2021 JogjaFile Inc.
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?