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

Click For Summary
A directed graph can only have an Eulerian circuit if it is strongly connected and each vertex has equal in-degree and out-degree. The misconception arises from confusing the properties of Euler circuits with disconnected graphs, which cannot satisfy the necessary conditions. Specifically, all vertices with nonzero degree must belong to a single strongly connected component. Additionally, the graph must allow for decomposition into edge-disjoint directed cycles. Understanding these conditions clarifies why connectivity is essential for the existence of an Euler circuit.
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.
 
Here is a little puzzle from the book 100 Geometric Games by Pierre Berloquin. The side of a small square is one meter long and the side of a larger square one and a half meters long. One vertex of the large square is at the center of the small square. The side of the large square cuts two sides of the small square into one- third parts and two-thirds parts. What is the area where the squares overlap?

Similar threads

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