In class, we learnt a method that helps us to show that there is no hamiltonian path (resp. cycle) in a graph. For the graph
(on the right side, it reads "$19$ vertices" and "$33$ edges")
it works like this:
A possible hamiltonian path $P$ for the $19$ vertices requires $18$ edges. None of the vertices $u_1, \ … \, u_7$ are adjacent. We have
$$d(u_1) = d(u_2) = d(u_3) = 6 $$
and
$$d(u_4) = d(u_5) = d(u_6) = d(u_7) = 3.$$
In $P$, every single one of these vertices can be an endvertex of at most two edges. The other edges don't require any attention, which are at least
$$3 \times 4 + 4 \times 1 = 16$$
edges. But we have
$$33 – 16 = 17,$$
and we can't connect $19$ vertices with $17$ edges, hence, there can't be a hamiltonian path.
Personally, I don't understand the argument that "every single one of these vertices can be an endvertex of at most two edges". Plus, I don't see how this calculations concerning edges that "don't require any attention" works.
Best Answer
The argument goes as follows. Suppose you have a path in the graph. For each vertex, the path can contain at most two edges meeting that vertex - the edge going to that vertex and the next edge which goes away from it. (There could only be one edge, if it is the first or last vertex on the path, or none, if it is not on the path at all, but there can't be more than two.)
Thus at most two of the six edges meeting $u_1$ are on the path, so at least four of these edges are not on the path. The same applies for $u_2$ and $u_3$, so at least $12$ of the $18$ edges meeting these vertices are not on the path. There is another one edge not on the path meeting each of $u_4$ to $u_7$, so in total there must be at least $16$ edges not on the path, so at most $17$ edges are on the path. But a path with at most $17$ edges has at most $18$ vertices, so it's not a Hamilton path.
This argument applies to any path you choose, so there is no Hamilton path in $G$.