0
15kviews
Give an example of graph which has

i. Eulenian circuit but not a hamiltanian circuit

ii Hamiltonian circuit but no a eulerian circuit

iii Both hamiltonian circuit and eulerian circuit


1 Answer
1
2.8kviews

Euler Circuit: An Euler circuit is a circuit that uses every edge of a graph exactly once and which starts and end on the same vertex.

Hamiltionian circuit: Hamiltonian circuit is a path that visits each vertex exactly once and which starts and ends on the same vertex.

Example:

Eulerian circuit but not a Hamiltionian circuit

enter image description here

n= number of vertices = 6 which is even.

$\therefore$ Euler circuit= a-b-c-d-e-f-a

ii. Hamiltonian circuit but not a Eulerian circuit

enter image description here

Hamiltonian circuit, a-b-c-d-e-f. No Eulerian circuit. The vertex 'a' is add degree.

ii. Both Hamiltonian circuit and Eulerian circuit

enter image description here

Hamiltonian circuit = a-b-c-d

Eulenian circuit = a-b-c-a-c-d-a

Please log in to add an answer.