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?
(a) For what values ofn (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?
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?
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?
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.
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.