# Graphs/Euler Path

### 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

# Notes

An Euler path of a graph G is a traversal of the graph that visits each **edge** of the graph exactly once.

An Euler tour, Euler circuit, or Euler cycle is an Euler path (i.e., a path that visits each edge once) that **also** starts and ends on the same vertex.

Determining if an Euler path or Euler tour of a graph exists is precisely the problem that led Euler to create the subject of graph theory in the first place. Euler was trying to tackle the Bridge of Königsberg problem, which was to determine if there is a walk through the different parts of Königsberg, connected by seven bridges, that requires the walker to cross each bridge (edge) exactly once.

## Undirected Graphs

For an undirected graph to be Eulerian, the number of vertices with odd degree **must** be 0 or 2.

Note that this is a special case of the First Theorem of Graph Theory, which states that the number of vertices with odd degree **must** be even.

According to Skiena:

- An undirected graph contains an Euler
**cycle**iff (1) it is connected, and (2) each vertex is of even degree - An undirected graph contains an Euler
**path**iff (1) it is connected, and (2) all but two vertices are of even degree. These two vertices will be the start and end vertices for the Eulerian path.

## Directed Graphs

How to check if a directed graph has an Euler tour?

According to Skienna,

- A directed graph contains an Euler cycle iff (1) it is strongly-connected, and (2) each vertex has the same in-degree as out-degree
- A directed graph contains an Euler path iff (1) it is connected, and (2) all vertices except two (x,y) have the same in-degree as out-degree, and (x,y) are vertices with in-degree one less than and one more than out-degree

## Using DFS

DFS can be used to tell if a graph is connected - or, for a directed graph, strongly connected.

For an undirected graph, a DFS should traverse every node if the graph is connected, so perform a DFS and check to make sure the number of vertices visited matches the number of vertices in the graph. If not, the graph is not connected and no Euler tour or Euler path exists.

For a directed graph, a random start node is selected, and a DFS is performed to ensure all nodes are reachable by u (start node), then DFS is performed on the transpose of the graph (every edge u,v reversed to v,u) to ensure all nodes can reach u.

See Graphs/DFS.

# Code

## Euler Tour Pseudocode

C = empty cycle at vertex 0 while G has unmarked edges: u = any vertex on C with unmarked edges C2 = empty list of edges v = u do: e = unmarked edge of v mark e append e to C2 v = other endpoint of e while v is not u Splice C2 into C at u end while

## Fleury's Algorithm

v = v0 F = E C = trivial path at v[0] while G has unmarked edges if v has unmarked edge that is not a bridge of V,F then e = unmarked edge of v that is not a bridge of V,F else e = any unmarked edge of v mark e append e to C F = F - e v = other endpoint of e end

# 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