algorithmgrapheuler-path

Directed Graph: Euler Path

Based on standard defination, Eulerian Path is a path in graph that visits every edge exactly once.

Now, I am trying to find a Euler path in a directed Graph. I know the algorithm for Euler circuit. Its seems trivial that if a Graph has Euler circuit it has Euler path. source:geeksforgeeks

[image source: geeksforgeeks.org]

So for above directed graph which has a Euler circuit also has Euler path.

Now if i remove an Edge lets say from 4 to 0 it is no more an Euler circuit.

  1. if start my DFS from vertex 0 i still have Euler Path.
  2. if start from vertex 3 i do not have Euler path

So, is it a requirement, that a directed graph has to be in Euler circuit to be an Euler path? I thought, Euler path should be less restrictive then Euler circuit.

Is there any directed graph which can be Euler path but not Euler circuit.

Solution

  • So, is it a requirement, that a directed graph has to be in Euler circuit to be an Euler path?

    No

    I thought, Euler path should be less restrictive than Euler circuit.

    Correct

    Is there any directed graph which can be Euler path but not Euler circuit.

    Yes

    I believe that your confusion is derived from the fact that when you DFS a directed graph starting from different nodes, you might get different results because some nodes might not be accessible when you start from different nodes. This has nothing to do with the definition of Eulerian path/trail. In order to "implement" the search for Eulerian path in a directed graph, you should run DFS from every node - and only if all the results returned False (no Eulerian path was found) then you know for sure that there is no Eulerian path. If there is an Eulerian cycle, there must be a node from which you can start DFS and find an Eulerian path.