Graph Theory37 sections · 1633 units
Open in Course

Conditions for Directed Graphs

When Euler paths exist in directed graphs.

For a directed connected graph:

Euler circuit exists if and only if every vertex has equal in-degree and out-degree.

Euler path exists if and only if:

  • At most one vertex has out-degree=in-degree+1\text{out-degree} = \text{in-degree} + 1 (this is the start)
  • At most one vertex has in-degree=out-degree+1\text{in-degree} = \text{out-degree} + 1 (this is the end)
  • All other vertices have equal in-degree and out-degree

Check connectivity: The underlying undirected graph must be connected (ignoring edge directions).