Are these graph Hamilton or not?

Question

I have read it a lot about that but I am still confusing how to find out if it is Hamilton graph or not. I have check here some similar examples but I was not able to understand it.

I know that a graph to be Hamilton it needs to do from one "starting" point we put to do all the graph until the end which is our "starting" point.

I have created those on a paper please help understand if those are Hamilton or not.

---

For these Graphs


Here I have created 1 and 2 as you can see graphs. As I have seen, if a graph has inside another circuit, then it is not a Hamilton. Is this right? As a result if there are similar like those with in, inside a "circle lets call it" then it is not a Hamilton graph?

---

And, for these Graphs


With 3 and 4, I am thinking to do a start point in an edge and to do all the graph until I end again on the "start point" but I see it that it is not happening. So my question is, are those Hamilton or not? My thought is that those 3 and 4 graphs are not Hamilton. If these are not Hamilton, how to understand it? (is this the way?). In the other hand if we want to make those Hamilton (if those are not) what should exactly need to change?

---

Is these Graph Hamilton? I guess it is.

---

Answer 1

The OP wants a Hamiltonian cycle, that is easy, for instance computing (using Mathematica):

g = Graph[{1 \[UndirectedEdge] 2, 1 \[UndirectedEdge] 3, 
   1 \[UndirectedEdge] 4, 2 \[UndirectedEdge] 3, 
   3 \[UndirectedEdge] 4, 3 \[UndirectedEdge] 5, 
   2 \[UndirectedEdge] 5, 4 \[UndirectedEdge] 6, 
   5 \[UndirectedEdge] 6, 4 \[UndirectedEdge] 7, 
   6 \[UndirectedEdge] 7, 6 \[UndirectedEdge] 8, 
   7 \[UndirectedEdge] 8, 5 \[UndirectedEdge] 8 },
  VertexCoordinates -> {{0, 2}, {1, 2}, {1/2, 3/2}, {0, 1}, {1, 
     1}, {1/2, 1/2}, {0, 0}, {1, 0}}]
HighlightGraph[g,FindHamiltonianCycle[g][[1]]]

For an arbitrary graph h, simply compute:

FindHamiltonianCycle[h]

If such a cycle exists, it will be returned. If not, the set of edges will be empty.

Here's a more complicated case:

Answer 2

It is easier to talk about the graphs if w give names to the vertices. So here they are again. To prove that a graph is Hamiltonian we specify a sequence of vertices that describe a Hamiltonian circle. Graph $5$ has the Hamiltonian Circle $$a-b-c-f-e-d-a$$

Graph $3$ has the Hamiltonian Circle $$b-a-c-d-f-g-h-e-b$$

It can be complicated to show that no Hamiltonian Circle exists. To lemmas about graphs and Hamiltonian Circles will help us:

Note 1:
If a vertex has degree $2$, that means that exactly two edges are incident to this vertex, then these two edges must be part of each Hamiltonian Circle of this graph.
Proof:
The vertex must be member of a Hamiltonian Circle, there must be one edge to enter the vertex and one edge to leave him. These are the both edges of this vertex.

Note 2:
If two edges incident to the same node are part of each Hamiltonian Circle, then all other edges incident to this vertex are not member of any Hamiltonian Circle. The edges can be removed from the graph and this new subgraph has the same Hamiltonian Circles as the original graph.
Proof:
For a Hamiltonian Circle for each vertex there are exactly to edges incident to these vertex that are member of the Hamiltonian Circle.

Let's apply this to Graph 4. Vertex $a$ has exactly two incident edges, so $a-b$ and $a-d$ are member of all Hamiltonian Circles. For similar reasons $c-b$ and $c-f$ are members of all Hamiltonian Circles. So $ba$ and $bc$ are members of all Hamiltonian Circles and so $be$ is not a member of any Hamiltonian Circle. Similar arguments show that $d-e$, $f-e$ and $h-e$ are not members of a Hamiltonian Circle. So $e$ cannot be a member of a Hamiltonian Circle. So there is not Hamiltonian Circle for this Graph 4.

These notes can also help us to construct Hamiltonian Circles. In Graph $1$ they show us that $i-n$ and $e-b$ are not part of an Hamiltonian Circle but the path $$e-k-i-h-d-b-a-g-m-n-p-f$$ is part of all Hamiltonian Circles. This path could easily compledted to a circle by adding the edges$f-c$ and $c-e$ to get the Hamiltonian Circle

$$e-k-i-h-d-b-a-g-m-n-p-f-c-e$$

In Graph $2$ we can show that $hi$, $f-n$, $d-m$, $b-k$ are not member of any Hamiltonian Circle, so no Hamiltonian Circle exists, because the circles $$a-b-c-d-e-f-g-h$$ and $$i-k-m-n$$ both must be contained in an a Hamiltonian Circle.