Hamiltonian Graphs | Hamiltonian Path | Hamiltonian Circuit

Hamiltonian Graph-

 

If there exists a closed walk in the connected graph that visits every vertex of the graph exactly once (except starting vertex) without repeating the edges, then such a graph is called as a Hamiltonian graph.

OR

Any connected graph that contains a Hamiltonian circuit is called as Hamiltonian Graph.

 

Example-

 

 

Hamiltonian Path-

 

  • If there exists a walk in the connected graph that visits every vertex of the graph exactly once without repeating the edges, then such a walk is called as Hamiltonian path.

OR

  • If there exists a path in a connected graph that contains all the vertices of the graph, then such a path is called as Hamiltonian path.

 

Note-

In Hamiltonian path, all the edges may or may not be covered but edges must not repeat.

 

Examples-

 

 

Hamiltonian Circuit-

 

  • If there exists a walk in the connected graph that visits every vertex of the graph exactly once (except starting vertex) without repeating the edges and returns to the starting vertex, then such a walk is called as Hamiltonian circuit.

OR

  • If there exists a cycle in a connected graph that contains all the vertices of the graph, then that cycle is called as Hamiltonian circuit.

OR

  • A Hamiltonian path which starts and ends at the same vertex is called as Hamiltonian circuit.

OR

  • A closed Hamiltonian path is called as Hamiltonian circuit.

 

Examples-

 

 

NOTES-

 

  • Any Hamiltonian circuit can be converted to a Hamiltonian path by removing one of its edges.
  • Every graph that has a Hamiltonian circuit also has a Hamiltonian path but vice versa is not true.
  • There may exist more than one Hamiltonian paths and Hamiltonian circuits in a graph.
  • Hamiltonian circuit is also sometimes called as Hamiltonian cycle.

 

PRACTICE PROBLEM BASED ON HAMILTONIAN GRAPHS-

 

Problem-

Which of the following is / are Hamiltonian graphs?

 

 

Solution-

 

A) 

The graph neither contains a Hamiltonian path nor it contains a Hamiltonian circuit.

Since, graph does not contain a Hamiltonian circuit, therefore graph is not a Hamiltonian Graph.

 

B) 

The graph neither contains a Hamiltonian path nor it contains a Hamiltonian circuit.

Since, graph does not contain a Hamiltonian circuit, therefore graph is not a Hamiltonian Graph.

 

C) 

The graph contains both a Hamiltonian path (ABCDHGFE) and a Hamiltonian circuit (ABCDHGFEA).

Since, graph contains a Hamiltonian circuit, therefore graph is a Hamiltonian Graph.

 

D) 

The graph contains both a Hamiltonian path (ABCDEFG) and a Hamiltonian circuit (ABCDEFGA).

Since, graph contains a Hamiltonian circuit, therefore graph is a Hamiltonian Graph.

 

E) 

The graph neither contains a Hamiltonian path nor it contains a Hamiltonian circuit.

Since, graph does not contain a Hamiltonian circuit, therefore graph is not a Hamiltonian Graph.

 

F) 

The graph contains both a Hamiltonian path (ABCDEFGHI) and a Hamiltonian circuit (ABCDEFGHIA)

Since, graph contains a Hamiltonian circuit, therefore graph is a Hamiltonian Graph.

 

Get more notes and other study material of Graph Theory.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
Hamiltonian Graphs | Hamiltonian Path | Hamiltonian Circuit
Article Name
Hamiltonian Graphs | Hamiltonian Path | Hamiltonian Circuit
Description
Any connected graph that contains a Hamiltonian circuit is called as Hamiltonian Graph. A closed Hamiltonian path is called as Hamiltonian circuit. Hamiltonian path is a path in a connected graph that contains all the vertices of the graph.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-