#Graph Theory

Question

Prove that following graph does not have Hamiltonian cycle.

Answer 1

 To show that a graph does not contain a Hamiltonian circuit (Hamiltonian Cycle):

1. A graph with a vertex of degree one cannot have a Hamiltonian circuit.

2. Moreover, if a vertex in the graph has degree two, then both edges that are incident with this vertex must be part of any Hamiltonian circuit.

3. A Hamiltonian circuit cannot contain a smaller circuit within it. 

So, in the given graph, vertices $b$ and $d$ have a degree of $2$. Therefore, edges $ab$, $bc$, $cd$ and $da$ must be included in any Hamiltonian circuit, according to Rule $2$.

Now, we have a smaller circuit (made up of edges $ab$, $bc$, $cd$ and $da$) already which is inside the Hamiltonian circuit, if the graph has any. So according to Rule $3$, the given graph can not have a Hamiltonian circuit.