1
$\begingroup$

I already proved a Euler Tour can't exist because all degrees would have to equal a number divisible by 2 but a Euler Path requires two odd degrees.

I still have to prove a graph exists that contains a Euler Path but doesn't contain a Hamilton Cycle/Path. I am new to Graph Theory which makes it really hard for me to think through the whole conditions existing there.

$\endgroup$
1
$\begingroup$

It helps to be familiar with some extremal examples of non-Hamiltonian graphs, and reasons why a graph might fail to be Hamiltonian. I'm just going to go over a few of them here, though not all of them will help.

For example, a graph might not be connected. That would do the job. It's not really useful here, though, because such a graph wouldn't have an Eulerian path either.

A graph might fail to have a Hamiltonian cycle because it has a cut vertex, such as the graph below. If you start on the left, for instance, then to visit all the vertices you have to go through the middle vertex to get to the other side, and then go through it again to get back to where you started. It does have a Hamiltonian path, though, so it might not be the right tool for the job here.

enter image description here

An unbalanced bipartite graph, such as the one below, does not have a Hamiltonian cycle because any path or cycle alternates between one part and the other, and you run out of vertices on one side long before you run out of vertices on the other side. If the bipartite graph is sufficiently unbalanced, it does not have a Hamiltonian path, either. The particular example I drew below is not Eulerian, but you can find a counterexample of this form if you play with it a bit.

enter image description here

Finally, the Petersen graph is a graph with no Hamiltonian cycle that's a counter-example to about a billion different things. It doesn't help us here, because all its vertices are odd, but I'm going to mention it anyway because it's so useful so often.

enter image description here

$\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.