Expert: Sherry Wallin - 7/1/2010

Question
Hello.
3 questions:
1) is ALWAYS true which a hamiltonian cycle with a odd number of vertices has a odd number of edges? If,yes why?
in particular:we have Number of edges = Number of vertices?
2) is POSSIBLE which a hamiltonian cycle with an even number of vertices has a odd number of edges?
3) Are 1) and 3) true also for EULERIAN cycles?

MY WORK:
about 1) It seems right.and seems Number of edges = Number of vertices.Is this right? However about the proof of this I have no idea.. (i tried to draw a graph with a limited number of vertices,but this is surely not a sufficient proof)
about 2)If is true which in a cycle:Number of edges = Number of vertices,then 2) should be false
about 3)I suppose yes,because the definition of cycle is the same in both Eulerian and Hamiltonian ones.

Thanks in advance

Answer
Manuel~
   
Since the number of vertices is an odd number let the number of vertices be 2n-1. This works because when n = 1 you have one vertex and the path (which is a loop that begins and ends with the vertex) is just one edge which is certainly odd too. Now suppose you have
2n -1 vertices then you have an edge from V1 to V2, V2 to V3,..,V(2n-2) to V(2n-1) AND a last edge from V(2n-1) back to V1 for a count of 2n-1 edges.

Think about what is means to be a Hamiltonian path: You must start and end at the same vertex and you must visit every other vertex exactly once. This forces the number of vertices to equal the number of edges regardless if the number of either is odd or even.

Since Eulerian cycles and Hamiltonian cycles are the same then what happens for the Hamiltonian cycle will most certainly occur for the Eulerian cycle.

Math Prof