0
$\begingroup$

For this graph, do Hamiltonian and Eulerian paths exist or not? enter image description here

Basic definition A cycle that uses every vertex in a graph exactly once is called a Hamilton cycle, and a path that uses every vertex in a graph exactly once is called a Hamilton path.

So I think it follows Hamilton path, is it correct?

EDIT:

To check whether these graph follows Eulerian circuit: A Euler circuit is a circuit that uses every edge of a graph exactly once. A Euler circuit starts and ends at the same vertex. enter image description here

$\endgroup$
2
$\begingroup$

Recall that an Eulerian path exists iff there are exactly zero or two odd vertices. Since $v_0$, $v_2$, $v_4$, and $v_5$ have odd degree, there is no Eulerian path in the first graph.

It is clear from inspection that the first graph admits a Hamiltonian path but no Hamiltonian cycle (since $\operatorname{deg}v_0=1$).

The other two graphs posted each have exactly two odd vertices, and so admit an Eulerian path but not an Eulerian circuit.

$\endgroup$
  • $\begingroup$ can you check the edit part.. for Euler circuit. from my knowledge uper one is not follows Euler circuit, and lower graph follows Euler circuit, is it correct? $\endgroup$ – Aadnan Farooq A Dec 10 '15 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.