Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 6 Marks

Year: May 2016

A path that visits each vertex in a graph exactly once is called a Hamiltonian path. If the Hamiltonian path begins and ends at the same vertex, the path is called a Hamiltonian circuit.

Problem:

No, the given graph does not have any Hamiltonian graph and Hamiltonian circuit because degree of each vertex is not greater than n/2. Also sum of degree of each pair of vertices is not greater than n-1, where n is the number of vertices.