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

82 Views Asked by At

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.

1

There are 1 best solutions below

2
On

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?