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

  • #1

Main Question or Discussion Point

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).
4zFle.png

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.

Thanks!
 

Answers and Replies

  • #2
87
138
Your example graph contains a zero degreed vertex, one of whose properties your quoted theorem is still missing.
  • A directed graph has an Eulerian cycle if and only if every vertex has equal in degree and out degree, and all of its vertices with nonzero degree belong to a single strongly connected component. Equivalently, a directed graph has an Eulerian cycle if and only if it can be decomposed into edge-disjoint directed cycles and all of its vertices with nonzero degree belong to a single strongly connected component.
Eulerian path and cycle or circuit.
 

Related Threads on Graph Theory: (proof)conditions for Euler Circuit in Digraph

Replies
1
Views
3K
Replies
5
Views
4K
  • Last Post
Replies
15
Views
4K
  • Last Post
Replies
3
Views
2K
Replies
3
Views
899
Replies
9
Views
6K
Replies
2
Views
1K
  • Last Post
Replies
6
Views
4K
  • Last Post
Replies
1
Views
763
Top