Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 6 Marks

Year: May 2014

Graph1

Here e and b are the two vertices with degree odd, and all other vertices have even degree. Hence there exists a Eulerian path:

Eulerian path: p q s v u r t s v q p u r p

The Hamiltonian path for the given diagram is as follows:

Hamiltonian path: t s q v u p r

Graph2

Here a and e are the two vertices with degree odd, and all other vertices have even degree. Hence there exists a Eulerian path:

Eulerian path: a c d a e b d e

The Hamiltonian path for the given diagram is as follows:

Hamiltonian path: a b e d c