Hamiltonian Graph

Example,

1. The above graph contains a cycle a-b-c-f-d-e-a that visits each vertex exactly once. Therefore, the cycle is a hamiltonian circuit.
2. This implies that the graph is a Hamiltonian Graph.

1. There exists a cycle in the graph that visits all vertices, a-b-d-c-f-d-e-a but vertex d appears twice in the cycle. Thus, it is not a Hamiltonian circuit.
2. The graph doesn’t contain a hamiltonian circuit. This implies that the graph is a Nonhamiltonian Graph.

1. The graph consists of 2 connected components – K1 and K2.
2. The two components are Hamiltonian but the graph as a whole is not.
3. We cannot reach from K1 to K2. No cycle can exist that visits all vertices of the graph.
4. Thus, the Graph is not hamiltonian.

1. The graph contains a Hamiltonian Path: e-a-b-d-c-f that visits each vertex exactly once but no cycle is formed. Thus, the graph is not Hamiltonian.

Important Facts

1. Every hypercube is a Hamiltonian.
2. Every cycle graph is Hamiltonian.
3. Every wheel graph is Hamiltonian.
4. Every complete graph ( v >= 3 ) is Hamiltonian.
5. Every complete bipartite graph ( except K_1,1 ) is Hamiltonian.

Properties of Hamiltonian Graph

1. Every Hamiltonian Graph contains a Hamiltonian Path but a graph that contains Hamiltonian Path may not be Hamiltonian Graph.
2. Every Hamiltonian Graph is a Biconnected Graph. It means that if we remove any vertex from the graph, the graph will remain connected. The graph may or may not remain Hamiltonian after removing the vertex. For example, if we remove a vertex from a cycle graph, the graph remains connected but it is no longer hamiltonian.

Applications of Hamiltonian Graph

1. Hamiltonian Graph can be used to find the most appropriate networks between different cities for road networking, pipelining purpose, etc.