Does there exist a graph G of order 10 and size 28 that is not Hamiltonian?

Question

I dont know how to tackle this problem. I can not think of anyway to start it, i cannot apply Dirac's equation to it because there will be many graphs of different degree sequence. But i have a graph in which one of this vertex has degree 4 which is less than the half of number of vertices. Is this right? Or is there any other way?

Answer 1

Here is a connected one that is obviously not hamiltonian.

In general: take your favorite graph on $9$ vertices and $27$ edges. Add one vertex and connect it to the rest. Done.

Answer 2

Dirac's theorem is a sufficient condition. So if it is not satisfied we can't say anything about Hamiltonicity of given graph.

An easy idea to make non-Hamiltonian graph is making graph disconnected. If you make a vertex of degree 0 and any set of edges on remaining 9 vertices you'll definitely get a non-Hamiltonian graph.

EDIT. There is also even 4-connected non-Hamiltonian graph on 10 vertices with 30 edges: