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

I Graph Theory: (proof)conditions for Euler Circuit in Digraph

  1. May 29, 2016 #1
    I have read in many places that one necessary condition for the existence of a Euler circuit in a directed graph is as follows.

    Theorem: "A directed graph has an eulerian circuit if and only if it is connected and each vertex has the same in-degree as out-degree."

    However, I don't understand why the state of being connected is a necessary condition. I thought that a Euler circuit is a closed walk where all of the edges are distinct and uses every edge in the graph exactly once. Therefore, the disconnected graph shown below should satisfy the condition of being a Euler circuit. (All the edges in the graph are used exactly once).
    Can anyone explain what I did wrong here? Also it would be greatly appreciated if someone could give a mathematical proof to both parts of the theorem.

  2. jcsd
  3. May 29, 2016 #2
    Your example graph contains a zero degreed vertex, one of whose properties your quoted theorem is still missing.
    Eulerian path and cycle or circuit.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted