# Graphs/Euler Circuit

### From charlesreid1

Euler path - a path around a graph that visits every edge of the graph exactly once.

- The following pages all redirect to Graphs/Euler Path:

Euler circuit/Euler cycle - an Euler path that starts and ends at the same vertex.

- The following pages all redirect to Graphs/Euler Circuit:

## Contents

# Overview

An Euler Circuit is an Euler path or Euler tour (a path through the graph that visits every edge of the graph exactly once) that starts and ends at the same vertex.

# Algorithm

## Undirected Graphs: Fleury's Algorithm

To print the Euler Circuit of an undirected graph (if it has one), you can use Fleury's Algorithm [1].

This algorithm is (where E is number of edges).

Step 1:

- Check that the graph has 0 or 2 odd vertices
- If there are any other number of odd vertices, no Euler circuit exists

Step 2:

- If there are 0 odd vertices, start at any node on the graph
- If there are 2 odd vertices, start at one of the odd vertices

Step 3:

- Follow edges one at a time.
- Edges can be classified as bridges (edges that lead to "dead end" nodes with only one edge) or non-bridges
- If you have a choice among multiple edges, choose the non-bridges first, leave the bridge edge for last.

Step 4:

- Stop when you run out of edges.

## Directed Graphs: Hierholzer's Algorithm

To print the Euler circuit on a directed graph, use the Hierholzer algorithm. It was published in 1873.

This algorithm is (where E is number of edges).

Links:

- https://en.wikipedia.org/wiki/Eulerian_path#Hierholzer.27s_algorithm
- https://math.stackexchange.com/a/2433946

Setup: ensure an Euler path can exist

- There should be a single vertex in graph which has (indegree + 1 == outdegree), this is the Euler path start vertex
- There should be a single vertex in graph which has (indegree == outdegree + 1), this is the Euler path end vertex
- Rest all vertices should have (indegree==outdegree)
- If any of above conditions fail, an Euler path cannot exist.

NOTE: What about the case of an Euler Cycle? Then all vertices have indegree==outdegree, but there is not a start/end vertex.

Setup: turn the Euler path into an Euler cycle

- If no edge from B to A exists, create an edge B -> A
- Now indegree == outdegree for all vertices

Algorithm:

- Choose any vertex v and push it onto the stack
- While stack is not empty, look at top vertex u on stack.
- If u has an unvisited edge (e.g., to vertex w), push the destination vertex w onto the stack, and mark the edge u-w as visited.
- If u has no unvisited edges, pop u off the stack and print it.
- When the stack is empty, you have printed sequence of vertices corresponding to Eulerian cycle

Clean-up:

- Check the length of the Eulerian cycle printed has a sufficient number of edges or not.
- If number of edges in cycle matches number of edges in graph, it is an Eulerian cycle.
- If number of edges in cycle mismatches number of edges in graph, the original graph may be disconnected (no Euler cycle/path exists)

Euler cycle vs Euler path:

- If no directed edge B -> A existed in the original graph, remove that edge from the graph and from the cycle to obtain the Euler path

# Related

Graphs:

- Graphs#Graph Traversals
- Graphs/Depth First Traversal
- Graphs/Breadth First Traversal
- Graphs/Euler Tour
- Graphs/Euler Circuit

Traversals on trees:

Breadth-first search and traversal on trees:

Depth-first search and traversal on trees:

OOP design patterns:

# Flags