Show that if $G$ is a graph of order $n \geq 2$ for which $\kappa (G) \geq \alpha(G)-1$, then $G$ has a Hamiltonian path.

Question

Show that if $G$ is a graph of order $n \geq 2$ for which $\kappa (G) \geq \alpha(G)-1$, then $G$ has a Hamiltonian path.

Theorem 3.15: Let $G$ be a graph of order at least 3. If $\kappa(G) \geq \alpha(G)$ then $G$ is Hamiltonian

The book tell me to let $H=G \bigvee K_1$ then consider theorem 3.15. ok so $H$ has order at least 3, but this doesn't change anything about $\kappa$ and $\alpha$, since $v \in K_1$ connected to every vertex in $G$, so $v$ can't be counted in $\alpha(H)$, same thing happen to $\kappa(H)$.

Even if $H$ is Hamiltonian, what does it have anything to do with $G$? $H$ isn't $G$ closure, Am I correct?

Answer 1

Hint:

Prove that $\kappa(H)=\kappa(G)+1$.

Prove that $\alpha(H)=\alpha(G)$.

Apply theorem 3.15.

Figure out how a Hamiltonian cycle in $H$ translates to a Hamiltonian path in $G$.