1. ## Euler cycle

I'm confused about the definition of a Euler cycle, my book says "a cycle in a graph G that includes all of the edges and all of the vertices of G is called an Euler cycle"

However on wikipedia it says "An Eulerian cycle, in an undirected graph is a cycle that uses each edge exactly once."

Which one is it?

If it is the latter, then is it possible to travel all the edges once and touch every vertex (not necessarily once) given the graph G has a Euler cycle? If so, how do you prove it?

Many thanks!

2. The Euler path visits each edge exactly once. The Euler cycle (or circuit) is an Euler path starting and ending on the same vertex. The Hamiltonian path visits each vertex exactly once.

Does your book define the Euler cycle in the context of a connected graph? If not, then it is simply impossible to visit all the vertices by visiting all the edges - you could have an isolated vertex somewhere.

3. Thanks for that.

In a theorem (in my book) after saying that sentence, it goes on to say "If a graph G has an Euler cycle, then G is connected and every vertex has an even degree"

I think I get it now. If a graph has a Euler cycle (following my books definition that the graph is connected and every vertex has an even degree) then a cycle which includes all the edges exactly once implies that each vertex will be touched at least once.

By being connected ensures there is no isolated vertex and to prove that each vertex has to be touched at least once, since the graph is connected, by traversing each edge once you will arrive at a vertex and by traversing ALL edges ensures that you will have touched every single vertex.

Is my understanding correct?

Thanks very much for your Ackbeet, I really appreciate it!

4. "If a graph G has an Euler cycle, then G is connected and every vertex has an even degree."

I just don't buy this statement. Consider the following graph: the completely connected graph of three vertices union one disconnected vertex. There is obviously an Euler circuit, because the degree of every vertex is two, except for the disconnected vertex with degree zero. All of these are even, hence there is an Euler circuit (it's pretty obvious what that circuit is).

I'll buy the statement that a graph having an Euler cycle implies every vertex has even degree. But I don't see how this rules out disconnected singleton vertices, unless you've restricted your domain of discourse only to connected graphs. So this whole thing could just be a matter of definition.

However, if you've got a connected graph already, then I would agree that an Euler path will touch every vertex.