Does this graph have Hamiltonian path and/or Eulerian paths?

2.7k Views Asked by At

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

1

There are 1 best solutions below

1
On BEST ANSWER

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.