Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Euler Circuits

  1. Sep 13, 2004 #1
    If a connected graph has a Euler circuit then this implies that all the vertices of the graph have even degree. Is the converse of this argument true? i.e. If a connected graph only contains vertices of even degree does this imply it contains an Euler Circuit?

    Could somebody please show me a proof (or counter-proof) of the above statement or at least direct me to a website that contains such a proof?

    Thanks.
     
  2. jcsd
  3. Sep 17, 2004 #2

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    well i believe it is well known that this is true so lets just prove it. maybe induction would work. so start with a graph with one edge, then it has to be a loop at one vertex hence it is true. oir do you allow loops?

    if not then we have at least two edges and two vertices and it again appears true. Ok now lets see,... how do we make the inductive step? well heck it seems obvious how to prove it... just start walking around the graph, beginning from anywhere. If we ever arrive twice at the same vertex say A, then there is a loop formed by the paths traversed between our first and second arrivals at A. Since no other path has ever been visited twice, this loop is a chain of paths formed by entering and leaving certain vertices.

    now erase all those poaths in that loop. That diminishes each vertex visited by exactly two edges. so we are left again with an even graph, possibly not connected. still by induction on the number of edges, every connected component of it has an euler circuit presumably beginning anywhere. so we seem to be able to cobble these together to get an euler circuit of the whole thing. well pretty ugly so far, but it seems perhaps true.

    this is probab;ly proved in essentially any book on elementary math, or just type in "bridges of konigsberg" to google.
     
  4. Sep 17, 2004 #3

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    gee, the coverage on the websites i found was so shallow that none proved the converse. but i think my argument essentially proves it. i.e. removing the partial circuit described, leaves a finite number of connected graphs, all even, so just go around your partial circuit and take side trips around any connected component of the complement as you come tot hem.

    'note that you may assume by induction that a circuit of an even graph may start and end anywhere. or just observe that this is obvious if there exists a circuit at all.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Euler Circuits
  1. Euler constants (Replies: 2)

  2. Euler totient puzzle (Replies: 2)

Loading...