1
$\begingroup$

An exercise in Chartand and Zhang asks to find a $2$-connected graph (that is, connected with order at least $3$ and no cut-vertices) that is Eulerian but not Hamiltonian (or prove none exists).

I was wondering whether the graph $K_{2, 4}$ works. I think it does. I have drawn a picture, and I think it is Eulerian because of the Theorem that states Eulerian iff all degrees have even degree (here, all vertices have degree $2$ or $4$). But I don't know how to justify $K_{2,4}$ not having a Hamiltonian cycle.

Can someone please help me?

$\endgroup$

1 Answer 1

0
$\begingroup$

Yes, that is a perfectly fine example. It is obvious that a cycle in a bipartite graph must have the vertices alternate between the two parts. Therefore, an unbalanced bipartite graph can never be Hamiltonian.

$\endgroup$

You must log in to answer this question.