Eulerian Path and Circuit
Task:
Given an undirected or a directed graph, find a path or circuit that passes through each edge exactly once.
Solution:
First let's see the conditions for an undirected graph:
 An undirected graph has an eulerian circuit if and only if it is connected and each vertex has an even degree (degree is the number of
edges that are adjacent to that vertex).
 An undirected graph has an eulerian path if and only if it is connected and all vertices except 2 have even degree. One of those 2 vertices
that have an odd degree must be the start vertex, and the other one must be the end vertex.
For a directed graph we have:
 A directed graph has an eulerian circuit if and only if it is connected and each vertex has the same indegree as outdegree.
 A directed graph has an eulerian path if and only if it is connected and each vertex except 2 have the same indegree as outdegree,
and one of those 2 vertices has outdegree with one greater than indegree (this is the start vertex), and the other vertex has indegree
with one greater than outdegree (this is the end vertex).
Algorithm for undirected graphs:
 Start with an empty stack and an empty circuit (eulerian path).
 If all vertices have even degree  choose any of them.
 If there are exactly 2 vertices having an odd degree  choose one of them.
 Otherwise no euler circuit or path exists.
 If current vertex has no neighbors  add it to circuit, remove the last vertex from the stack and set it as the current one. Otherwise
(in case it has neighbors)  add the vertex to the stack, take any of its neighbors, remove the edge between selected neighbor and that
vertex, and set that neighbor as the current vertex.
 Repeat step 2 until the current vertex has no more neighbors and the stack is empty.
Note that obtained circuit will be in reverse order  from end vertex to start vertex.
Algorithm for directed graphs:
 Start with an empty stack and an empty circuit (eulerian path).
 If all vertices have same outdegrees as indegrees  choose any of them.
 If all but 2 vertices have same outdegree as indegree, and one of those 2 vertices has outdegree with one greater than its indegree,
and the other has indegree with one greater than its outdegree  then choose the vertex that has its outdegree with one greater than
its indegree.
 Otherwise no euler circuit or path exists.
 If current vertex has no outgoing edges (i.e. neighbors)  add it to circuit, remove the last vertex from the stack and set it as
the current one. Otherwise (in case it has outgoing edges, i.e. neighbors)  add the vertex to the stack, take any of its neighbors,
remove the edge between that vertex and selected neighbor, and set that neighbor as the current vertex.
 Repeat step 2 until the current vertex has no more outgoing edges (neighbors) and the stack is empty.
Note that obtained circuit will be in reverse order  from end vertex to start vertex.
Both algorithms will give you the tour in reverse order, i.e. from the end vertex to the start vertex.
As you can see  the algorithms are very similar.
Complexity:
The complexity of both algorithms is O(N+M), where N is the number of vertices and M is the number of edges.
Sample Execution:

Given:
A sample undirected graph made in Graph Magics.
Below execution steps of this algorithm are shown (all images are created in Graph Magics). 

Legend:
 current vertex is surrounded by red color Starting state:
Stack: empty
Location: none
Circuit: empty 
Download this graph (viewable with Graph Magics)


Because all vertices have even degrees, we can select any vertex as start point. Let it be 1. Current
state:
Stack: empty
Location: 1
Circuit: empty 


Go to vertex 2 (a neighbor of 1), add 1 to the stack, delete the edge between 1 and 2. Current state:
Stack: 1
Location: 2
Circuit: empty 


Go to vertex 3, add 2 to the stack, delete the edge between 2 and 3. Current state:
Stack: 1, 2
Location: 3
Circuit: empty 


Go to vertex 4, add 3 to the stack, delete the edge between 3 and 4. Current state:
Stack: 1, 2, 3
Location: 4
Circuit: empty 


Go to vertex 2, add 4 to the stack, delete the edge between 4 and 2. Current state:
Stack: 1, 2, 3, 4
Location: 2
Circuit: empty 


Go to vertex 8, add 2 to the stack, delete the edge between 2 and 8. Current state:
Stack: 1, 2, 3, 4, 2
Location: 8
Circuit: empty 


Go to vertex 1, add 8 to the stack, delete the edge between 8 and 1. Current state:
Stack: 1, 2, 3, 4, 2, 8
Location: 1
Circuit: empty 


Go to vertex 6, add 1 to the stack, delete the edge between 1 and 6. Current state:
Stack: 1, 2, 3, 4, 2, 8, 1
Location: 6
Circuit: empty 


Go to vertex 9, add 6 to the stack, delete the edge between 6 and 9. Current state:
Stack: 1, 2, 3, 4, 2, 8, 1, 6
Location: 9
Circuit: empty 


Go to vertex 1, add 9 to the stack, delete the edge between 9 and 1. Current state:
Stack: 1, 2, 3, 4, 2, 8, 1, 6, 9
Location: 1
Circuit: empty 


Because vertex 1 (current location) has no more neighbors left  we add it to the circuit, take the vertex from the top of the stack
(i.e. vertex 9), and set it as the current location. Current state:
Stack: 1, 2, 3, 4, 2, 8, 1, 6
Location: 9
Circuit: 1 


Vertex 9 has no neighbors left. Thus we add it to the end of the circuit, remove vertex 6 from the stack and set it as the current
location. Current state:
Stack: 1, 2, 3, 4, 2, 8, 1
Location: 6
Circuit: 1, 9 


Vertex 6 has no nieghbors left. Add it to the circuit, remove 1 from the stack and set it as the current location. Current
state:
Stack: 1, 2, 3, 4, 2, 8
Location: 1
Circuit: 1, 9, 6 


Add 1 to the circuit, go to vertex 8 and remove it from the sack. Current state:
Stack: 1, 2, 3, 4, 2
Location: 8
Circuit: 1, 9, 6, 1 


Now 8 has still some more neighbors left. We take one of them  let it be 5.
Add 8 to the stack, go to vertex 5 and delete the edge between these two vertices. Current state:
Stack: 1, 2, 3, 4, 2, 8
Location: 5
Circuit: 1, 9, 6, 1 


Go to vertex 7, add 5 to the stack and delete the edge between these two vertices.
Current state:
Stack: 1, 2, 3, 4, 2, 8, 5
Location: 7
Circuit: 1, 9, 6, 1 


Go to vertex 8, add 7 to the stack and delete the edge between these two vertices. Current state:
Stack: 1, 2, 3, 4, 2, 8, 5, 7
Location: 8
Circuit: 1, 9, 6, 1 


Note that no more edges are left, so next steps will only take last vertex from the stack and will add it to the circuit.
Add 8 to the circuit, return to vertex 7 and remove it from the stack. Current state:
Stack: 1, 2, 3, 4, 2, 8, 5
Location: 7
Circuit: 1, 9, 6, 1, 8 


Add 7 to the circuit, return to 5 and remove it from the stack. Current state:
Stack: 1, 2, 3, 4, 2, 8
Location: 5
Circuit: 1, 9, 6, 1, 8, 7 


Add 5 to the circuit, return to 8 and remove it from the stack. Current state:
Stack: 1, 2, 3, 4, 2
Location: 8
Circuit: 1, 9, 6, 1, 8, 7, 5 


Add 8 to the circuit, return to 2 and remove it from the stack. Current state:
Stack: 1, 2, 3, 4
Location: 2
Circuit: 1, 9, 6, 1, 8, 7, 5, 8 


Add 2 to the circuit, return to 4 and remove it from the stack. Current state:
Stack: 1, 2, 3
Location: 4
Circuit: 1, 9, 6, 1, 8, 7, 5, 8, 2 


Add 4 to the circuit, return to 3 and remove it from the stack. Current state:
Stack: 1, 2
Location: 3
Circuit: 1, 9, 6, 1, 8, 7, 5, 8, 2, 4 


Add 3 to the circuit, return to 2 and remove it from the stack. Current state:
Stack: 1
Location: 2
Circuit: 1, 9, 6, 1, 8, 7, 5, 8, 2, 4, 3 


Add 2 to the circuit, return to 1 and remove it from the stack. Current state:
Stack:
Location: 1
Circuit: 1, 9, 6, 1, 8, 7, 5, 8, 2, 4, 3, 2 


The stack is empty and 1 has no more neighbors. So this is the last point in this eulerian tour.
Finally add 1 to the circuit.
Circuit: 1, 9, 6, 1, 8, 7, 5, 8, 2, 4, 3, 2, 1
Here the order doesn't matter, but for directed graphs  it's crucial.
So let's consider the Eulerian Tour for this graph to be the reverse of the above circuit:
1, 2, 3, 4, 2, 8, 5,
7, 8, 1, 6, 9, 1


Applications:
 A postman has to visit a set of streets in order to deliver mails and packages. It is needed to find a path that starts and ends at
the postoffice, and that passes through each street (edge) exactly once. This way the postman will deliver mails and packages to all
streets he has to, and in the same time will spend minimum efforts/time for the road.
Note: not all graphs have an eulerian circuit. If needed  the algorithm for Chinese Postman Problem can be used.
