Results 1 to 4 of 4

Math Help - Euler cycle

  1. #1
    Senior Member
    Joined
    Apr 2009
    Posts
    308

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    5
    Awards
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Apr 2009
    Posts
    308
    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!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    5
    Awards
    2
    "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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Euler and Hamiltonian Cycle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 21st 2010, 04:56 AM
  2. Euler path and Euler circuit problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 19th 2010, 09:18 PM
  3. Replies: 0
    Last Post: February 20th 2010, 09:26 AM
  4. Replies: 0
    Last Post: September 17th 2009, 07:44 PM
  5. Replies: 2
    Last Post: December 9th 2007, 03:33 PM

Search Tags


/mathhelpforum @mathhelpforum