# Need prove a Graphs with n >= 5 with a Euler path and without Hamilton Path and Hamilton Cycle exist.

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.

## 1 Answer

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