Are there any conditions that are necessary for the existence of a Hamiltonian path in a graph?

Question

I'm aware of some things that tell us that there is a Hamiltonian cycle in a graph (for example, if all of the $n$ vertices have a degree greater than $n/2$), but are there any conditions that conclusively tell us that the graph does not have any Hamiltonian cycles (or paths)?

Answer 1

Hamiltonian cycle implies biconnected, which in turn implies that every node has degree at least two.

Hamiltonian path implies connected and at most two nodes of degree one.

Answer 2

A tough graph is a graph $G$ such that deleting any $k$ vertices leaves at most $k$ connected components. All Hamiltonian graphs are tough, because the cycle graph $C_n$ is tough, and adding additional edges cannot destroy this property.

Being tough is not sufficient to be Hamiltonian (see, e.g., this previous answer of mine), but still the most common ways to show that a graph isn't Hamiltonian also imply that it isn't tough. Some examples:

• Disconnected graphs, and graphs with a cut vertex, are neither tough nor Hamiltonian. (A special case of this is that vertices of degree $1$ cannot appear in Hamiltonian graphs.)
• Bipartite graphs with $a$ vertices on one side and $b \ne a$ vertices on the other side are neither tough nor Hamiltonian. (If $b>a$, then we can delete the $a$ vertices on one side and be left with $b$ connected components.)

Since $P_n$ has the property that deleting any $k$ vertices leaves at most $k+1$ connected components, we can write down a similar necessary condition for traceable graphs (graphs with a Hamiltonian path), but these are considered less often and there's not a short name for this necessary condition.