Connectivity of a Hamiltonian path

405 Views Asked by At

Show that if G has a Hamiltonian path then for every proper subset S of V, $\,$ $\omega(G-S)\leq\vert S \vert + 1$,$\,$where V is the set of the vertices of G and $\omega$ is the number of the components of G. (from Graph Theory With Applications, Bondy, Murty, 1976)

1

There are 1 best solutions below

3
On

Suppose $G$ has a Hamiltonian path $H$. Then, $\omega(G-S) \leq \omega(H - S)$. Can you bound the size of $\omega(H-S)$?