[Math] What are the necessary and sufficient conditions for Euler path in directed graph

directed graphsdiscrete mathematicseulerian-pathgraph theory

The definition says
"A directed graph has an eulerian path if and only if it is connected and each vertex except 2 have the same in-degree as out-degree, and one of those 2 vertices has out-degree with one greater than in-degree (this is the start vertex), and the other vertex has in-degree with one greater than out-degree (this is the end vertex)."

But i need to understand that is it that by connected,does it mean strongly connected or unilaterally connected?

Best Answer

The exact condition you need is that every vertex must be reachable from the start vertex (except for any vertices with in-degree and out-degree $0$, which we don't care about when looking for an Euler path). Equivalently, every edge must be reachable from the start vertex. That is, for every edge, there is a path from the start vertex including that edge.

This condition is clearly necessary; if an edge is not reachable from the start vertex, you can never include that edge in a directed path. You can verify that this condition is sufficient by checking that a modified version of Hierholzer's algorithm (Wikipedia link) will find an Euler path.

Hierholzer's algorithm, modified for Euler paths in directed graphs, starts by taking an arbitrary path from the start vertex to the end vertex. Then, as long as there are vertices on the path with unused out-edges, we:

  1. Start at one of these vertices and keep taking unused out-edges until we return to that vertex, creating a directed cycle;
  2. Splice that cycle into our path from the start vertex to the end vertex, creating a longer path.

The degree condition ensures that we never get stuck in step 1. But it's the connectedness condition given above that ensures that, as long as there are unused edges anywhere in the graph, there must be unused edges leaving vertices on the path we've found.