1
$\begingroup$

Definitions of both:

Hamiltonian Circuit: Visits each vertex exactly once and consists of a cycle. Starts and ends on same vertex.

Eulerian Circuit: Visits each edge exactly once. Starts and ends on same vertex.

Is it possible a graph has a hamiltonian circuit but not an eulerian circuit?

Here is my attempt based on proof by contradiction:

Suppose there is a graph G that has a hamiltonian circuit. That means every vertex has at least one neighboring edge. <-- stuck

$\endgroup$
6
$\begingroup$

Take a graph which is just a cycle on at least 4 vertices, then add an edge between one pair of vertices. Where you added the edge, you will have an odd degree, so the graph cannot have an Eulerian cycle. But the original cycle gives a Hamiltonian cycle.

Another example: the complete graph on $n$ vertices, when $n$ is even.

$\endgroup$
0
$\begingroup$

The theta graph: $\Theta$. Four more characters to be postable.

$\endgroup$

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.