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

Click For Summary
SUMMARY

A directed graph possesses an Eulerian circuit if and only if it is strongly connected and each vertex has equal in-degree and out-degree. The discussion clarifies that a disconnected graph cannot satisfy the conditions for an Euler circuit, as all vertices with non-zero degree must belong to a single strongly connected component. Additionally, the theorem states that a directed graph can be decomposed into edge-disjoint directed cycles, reinforcing the necessity of connectivity for Eulerian properties.

PREREQUISITES
  • Understanding of directed graphs and their properties
  • Familiarity with in-degree and out-degree concepts
  • Knowledge of strongly connected components in graph theory
  • Basic comprehension of Eulerian paths and circuits
NEXT STEPS
  • Study the concept of strongly connected components in directed graphs
  • Learn about Eulerian paths and circuits in depth
  • Explore mathematical proofs related to graph theory theorems
  • Investigate edge-disjoint cycles and their implications in directed graphs
USEFUL FOR

Mathematicians, computer scientists, and students studying graph theory, particularly those interested in the properties of directed graphs and Eulerian circuits.

lem0ncheezcake
Messages
3
Reaction score
0
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!
 
Mathematics news on Phys.org
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.
 

Similar threads

  • · Replies 34 ·
2
Replies
34
Views
6K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 3 ·
Replies
3
Views
1K
  • · Replies 2 ·
Replies
2
Views
5K
  • · Replies 1 ·
Replies
1
Views
413
  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 22 ·
Replies
22
Views
4K
  • · Replies 10 ·
Replies
10
Views
3K