Graph Theory

Eulerian Path

An Eulerian path is a path that goes through each edge exactly once.

An Eulerian cycle/circuit is an Eulerian path that starts and ends at the same node (a cycle that uses each edge exactly once).

An Eulerian trail/ Euler walk is a walk that uses each edge exactly once. If such a walk exists, the graph is called traversable or semi-eulerian.

We can find the Eularian Path using Hierholzer’s Algorithm.

• https://cp-algorithms.com/graph/euler_path.html

Euler Tour of Tree

I initially confused this because I thought it was very similar to pre-order Tree Traversal. While the way you travel between the edges is the same, in pre-order traversal you are only “visiting” each node once, whereas in Euler Tour you store the revisited node every time you go up a higher level.

With the Euler tour you can derive additional information from the result.

Let’s say you have the tree:

     A
    / \
   B   E
  / \   \
 C   D   F

For prev-order traversal, it would be:

A -> B -> C -> D -> E -> F

If you performed the euler tour algorithm, it would be:

A -> B -> C -> B -> D -> B -> A -> E -> F -> E -> A

To compute the Euler Tour, just do DFS starting from the root node but add the current node as well to the list of visited every time.

https://usaco.guide/gold/tree-euler?lang=cpp There is this idea of using the timer to get the depth.

Eulerian Circuit / Euler Tour

Definition

An Eulerian circuit (or Euler tour) of a graph $G$ is a closed walk that contains every edge of $G$ exactly once.

Used in Connected Graph.

Theorem 4.9.2

Let $G$ be a connected graph. Then, $G$ has an Eulerian Circuit if and only if every vertex has even degree.

Related

• Hamiltonian Path