Necessary condition for Hamiltonian path

Question

Determining a graph does not contain Hamiltonian path is very difficult. See for example this particular graph.

This sufficient condition for Hamiltonian path found in this link ClickHere does not satisfy, but does not guarantee that $G$ does not contain Hamiltonian path. So, how do we say that $G$ is does not contain Hamiltonian path? Lastly, I found a thereom stated as : Let $G$ be a graph with a Hamiltonian path . Then, if we delete any $k$ vertices of $G$, the resulting graph will have at most $k+1$ components. {reference ClickHere}. This is necessary condition for the existence of Hamiltonian path?. Where can i find the reliable source that stated this theorem? Thanks in advance

Answer 1

Almost no source you consult will state this theorem directly. That's because Hamiltonian cycles are more important, and the corresponding theorem for cycles is much more well-known:

(Chvátal, 1973) If $G$ has a Hamiltonian cycle. Then for any nonempty $S \subseteq V(G)$, $G-S$ has at most $|S|$ components.

This can be found in textbooks as well. I have West's Introduction to Graph Theory handy, and it is Proposition 7.2.3 there.

Generalizing this to paths can be done by imitating the proof of Chvátal's result with minor modifications. We can also use the theorem about cycles to deduce the generalization to paths as a corollary, using an observation like the following:

(West, Remark 7.2.16) $G$ has a Hamiltonian path if and only if the join $G \vee K_1$ has a Hamiltonian cycle.

It is a pretty short proof either way. See this question on MSE. In West's textbook it is left as an exercise (Exercise 7.2.4), and in situations where you need to cite a source, it is not out of the question to cite an exercise in a textbook.