**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**.