Expert: Sherry Wallin - 6/28/2010

Question
Hello.I just sent you a question about Chinese Remainder Theorem:I'm reading the answer and then I'll surely thank you (for your very detailed explanation).
The question of today is:
In my book: (graphs connected,undirected)
walk = serie of vertex (distinct or not doesn't matter)
path = serie of vertex (ALL DISTINCT)
cycle = is a path with first and last vertex NOT DISTINCT

And this is very clear...
MY QUESTION IS:
What is the difference between eulerian walk/path/cycle and hamiltonian walk/path/cycle (in total:6).
I know the general definition of "Eulerian" (every edge),"Hamiltonian" (every vertex) but not the differences about walk/path/cycle in Eulerian or Hamiltonian (I hope the question is clear).

In particular I have 2 theorem I can't understand what "type of Eulerian" are referred to:
1)(needed and sufficient to have a "Eulerian") x:starting vertex,y:ending vertex. if x!=y,x and y have to have ODD degree while each other vertex has EVEN degree.
if x=y each vertex has to have EVEN degree.
2) A "Eulerian" cycle exists if and only if EACH vertex has EVEN degree.

IN MY BOOK:
1) is about a "Eulerian PATH",but already this isn't ok because path = each vertex distinct
2) is about a "Eulerian CYCLE",and this sounds possible to me.

Can you help me to understand these things better,please?
Thanks again

Answer
Manuel~
   
    First off you say that an Eulerian path means each vertex is distinct but an Eulerian  path is a path whose graph visits each edge exactly once. This can happen in more than one way:

    say you start at vertex A and go to vertex B then from vertex B to vertex C and there is no edge connecting vertex C to vertex A and there is only one edge from A to B and B to C. Here there were 2 edges and they were each visited only once, thus it is definitely Eulerian. Now suppose you did exactly the same except there was one and only one edge from vertex C back to vertex A. This is still Eulerian because each edge was visited exactly once BUT vertex A in NOT DISTINCT is it? Think a bit about this...

    About 2...if x!=y then you could have an Eulerian or not depending if there is an edge between x and y (see above). In the first half of the example I used there are two vertices of odd degree (A->B and B ->C) and one vertex of even degree (2 edges off of vertex B:
b ->A and B ->C since this is an undirected graph), and in the second half of the example all the vertices are of even degree, that is, there are 3 vertices of even degree. If you want to think of a cycle as a closed path you can. Then it makes sense that you will need to come and go from each vertex in order to 'close' the path.

    And finally you asked about the differences between Eulerian and Hamiltonian. First in Hamiltonian there is a path called simple which means that no vertex is repeated, therefore this is similar to the first half of my example, it would be a Hamiltonian path where every vertex is visited exactly once. Cycles are the same in that a Hamiltonian cycle requires that you begin and end with the same vertex.

I hope this helps you a bit in clarification.

Math Prof