Thread: Eulerian and hamiltonian questions

(a) For what values of

n (where n => 3) does the complete graph Kn have an Eulerian
tour? Justify your answer.
(b) For what values of n (where n => 3) does the complete graph Kn have a Hamiltonian

cycle? Justify your answer.

I have no idea what these questions mean. Are the questions referring to a particular graph that I should have or are they just general questions? Please help!

The complete graphs Kn are those simple undirected graphs where all the vertices have exactly one edge connecting them to each of the other vertices. That is, every distinct pair of vertices is connected with one edge.

Does this help?

Is the answer to a) all of them and the answer to b) none of them? Or am I completely off? I still don't know how you can tell.

No. I think some will have them, others won't. What is the criteria, you might ask? Look here for Euler tours, and here for Hamiltonian cycle. How can you do this sort of counting for the complete graphs Kn?

I know the definitions for the two kinds but I still can't see the answers. Obviously when n = 3 there is a eulor tour, but how do I know for the others? I'm so confused.

What are the necessary conditions that a graph have an Euler tour? Hamiltonian cycle?

For a eulor tour, the path meets each edge only once and starts and finishes on the same vertex. For the hamiltonian cycle the path meets each vertex only once and starts and finishes at the same vertex...

Your first definition is for the Euler cycle, not the Euler tour. The tour doesn't have to start and end on the same vertex, although it is allowed to do so. So an Euler cycle is an Euler tour, but not necessarily vice versa. Your Hamiltonian cycle definition is correct.

But what you need now are practical ways to determine if a graph has an Euler tour or a Hamiltonian cycle. How about a numerical criterion?

Originally Posted by Ackbeet

Your first definition is for the Euler cycle, not the Euler tour. The tour doesn't have to start and end on the same vertex, although it is allowed to do so. So an Euler cycle is an Euler tour, but not necessarily vice versa. Your Hamiltonian cycle definition is correct.

But what you need now are practical ways to determine if a graph has an Euler tour or a Hamiltonian cycle. How about a numerical criterion?

An Euler tour and an Euler cycle/circuit are the same thing.

In graph theory, an Eulerian path is a path in a graph which visits each edge exactly once. Similarly, an Eulerian circuit is an Eulerian path which starts and ends on the same vertex. - wiki

Well there isn't one specified aside from the n >= 3 do I just go up to n = 12?

Sorry just letting you know its 4am in the morning where I am and I'm trying to get this done now so sorry if I ask dumb questions!!!

Ah, I see.

An Eulerian path, Eulerian trail or Euler walk in an undirected graph is a path that uses each edge exactly once. . .

An Eulerian cycle, Eulerian circuit or Euler tour in an undirected graph ...

So, path = trail = walk, and cycle = circuit = tour.

Originally Posted by Ackbeet

In graph theory, an Eulerian path is a path in a graph which visits each edge exactly once. Similarly, an Eulerian circuit is an Eulerian path which starts and ends on the same vertex. - wiki

Yes, but tour means cycle.

Originally Posted by Ackbeet

Ah, I see.

An Eulerian path, Eulerian trail or Euler walk in an undirected graph is a path that uses each edge exactly once. . .

An Eulerian cycle, Eulerian circuit or Euler tour in an undirected graph ...

So, path = trail = walk, and cycle = circuit = tour.

Exactly.

You can have an Euler tour if and only if the graph is connected and all vertices have even degree. So which complete graphs satisfy this requirement?

For the Hamiltonian, I think you can see that all you really need is the ability to come back on yourself. Hence, K1 and K2 don't fit the bill. However, K3 on up work because you can just traverse the "outside", so to speak, and end up where you started.