DEV Community: Muhammad Taaha Tariq

Eulerian Paths Explained: From Königsberg to Hierholzer’s Algorithm

Muhammad Taaha Tariq — Tue, 02 Sep 2025 16:44:03 +0000

Imagine standing on an archipelago, its islands connected by bridges, and facing a seemingly simple question: can you start at one point, cross each bridge exactly once, and return to where you began?

This puzzle, first posed in the city of Königsberg, puzzled mathematicians for years until Euler provided a groundbreaking solution. His work gave birth to what we now call Euler paths and Euler circuits — fundamental concepts in graph theory.

To make the discussion clearer, let's first go over some important definitions.

Incidence

Considering the same problem, imagine standing on one of the bridges and asking yourself where you can go from there. This idea of a bridge being connected to a landmass is exactly what incidence means.

Definition: An edge is said to be incident to a vertex if that vertex is one of the edge's endpoints.

And to get an idea of the number of ways to get to a landmass through bridges is what we commonly refer to as the degree of a vertex or landmass in this context.

Definition: Degree of a vertex refers to the number of edges incident to that vertex, denoted as deg(v).

A loop is counted twice in the degree of a vertex since both its edges are incident to the same vertex.

In the context of a directed graph, we differentiate between out-degrees and in-degrees since the edges offer a unidirectional connection. In-degree of a vertex counts the number of ways to get into that vertex, whereas Out-degree counts the number of ways to get out of that vertex. An important thing to note is that if we were to sum up the in-degrees and out-degrees of all the vertices, then they would be equal. To see why, consider the directed edge as a one-way road; such a road must have a starting point and an endpoint (the vertices), and the same is true for all directed edges.

\sum_{v \in V} \deg^+(v) = \sum_{v \in V} \deg^-(v)

where V is the vertex set.

These definitions motivate a theorem, commonly referred to as the first theorem of graph theory or the Handshake theorem.

Theorem: In an undirected graph, the sum of the degrees of all its vertices is equal to twice the number of edges in the graph.
$\sum_{v \in V} \deg(v) = 2 \times |E|$

It follows from the fact that each edge has two endpoints and so, contributes two to the degrees of the graph. This theorem provides insight into the graph structure and allows us to validate graph configuration, and is also useful in graph coloring.

Eulerian Path/Circuit

To get an intuition of what a path means in graph theory, imagine starting from an island and going around the archipelago, following the bridges, and ending at some island, not necessarily the one you started from (if so, then it is called a circuit), but the bridges and islands can not be revisited. This traversal of islands constitutes a path.

Definition: A path is a sequence of distinct vertices joined by distinct edges, representing a traversal of the graph.

A circuit is a path whose starting and ending vertices is the same.

The path depicted in figure 1 can be thought of as the sequence of vertices A, B, C, E where there is an undirected edge between (aᵢ₋₁, aᵢ) but the directed edges indicate the path traversal.

Now that we are done with the preliminary definitions and concepts, we turn to the crux of the article.

Definition: An Euler path is a path that visits each edge exactly once.

An Euler circuit is defined in the same way, with the additional constraint that it must start and end at the same vertex.

Existence

Criteria 1

For an Euler path to exist, the graph must be connected. If it has an isolated subgraph, then such a subgraph must not have any edges. This is because if isolated subgraphs have distinct edges, then any path through the graph can't traverse all of these isolated subgraphs.

If we start from any bᵢ we can only traverse the bⱼ's where j = 1, 2, 3, 4 vertices and not the (aᵢ, aⱼ) edges. Similarly for aᵢ's.

Criteria 2

For a directed graph, the difference between deg⁺(v) and deg⁻(v) must be less than two, that is |deg⁺(v) - deg⁻(v)| < 2, for if it is two or greater, not all the edges can be traversed.

To see why, consider the case where deg⁺(v) = 2 and deg⁻(v) = 4.

There are two ways into the vertex and four out of it, so even if you were to start from this vertex, you can at most cover three of the four outgoing vertices.

Criteria 3

For all the vertices excluding the starting and the ending vertex, the deg⁺(v) must be equal to deg⁻(v); this ensures that for every way into the vertex, there's a way out. If this is true for the starting and ending vertices as well, then we have an Euler circuit. Otherwise, we can have deg⁻(v) - deg⁺(v) = 1 for the starting vertex, which ensures that for every edge entering the vertex, there is a corresponding way out, with one additional outgoing edge reserved for the initial move. Similarly, for the ending vertex, we can have deg⁺(v) - deg⁻(v) = 1.

Consider the sequence of vertices s, a, b, c, a, d, t.

For an undirected graph, this can be succinctly expressed as:
"There's an Euler path if the degree of exactly two of the vertices is odd, and an Euler circuit if the degree of none of the vertices is odd".

Hierholzer's Algorithm

The basic idea of Hierholzer's algorithm is the stepwise construction of the Eulerian path by connecting disjoint cycles.

First, we ensure that an Euler path or circuit exists by the above-stated criteria. If either one fails, then we can't have an Euler path or circuit.

Algorithm

Begin at a starting vertex (the designated start if one exists, otherwise any vertex with edges). Follow edges successively, choosing each edge only once, until you can no longer continue. This produces an initial trail that either forms a closed cycle (Euler circuit case) or ends at the terminal vertex (Euler path case).
If there remain unused edges, find a vertex on the current trail that still has unvisited outgoing edges. From this vertex, construct another trail in the same way, and then splice it into the original trail. Repeating this process until all edges are used yields the Euler path or circuit.

Link to Hierholzer's algorithm's implementation in different languages: Implementation of the algorithm.

Conclusion

Euler paths and circuits arise in many applications throughout computer science and other disciplines, where they can be used to find optimal routes minimizing travel distance and ensuring complete coverage of an area, amongst others, and it is of utmost importance to find an efficient solution to this problem, something that this algorithm offers to do in O(E) time complexity.

References

Königsberg Bridges Problem - Wikipedia: Overview of the historical problem that inspired Euler's work on graph theory.
Graph Theory - Handshaking Lemma - Wikipedia: Explanation of the Handshake Theorem, including the sum of degrees and its applications.
Hierholzer's Algorithm - Rosetta Code: Implementation examples of Hierholzer’s algorithm for finding Eulerian paths and circuits in different programming languages.

Understanding Tarjan’s Algorithm with Visual Examples

Muhammad Taaha Tariq — Fri, 29 Aug 2025 12:03:52 +0000

Tarjan's algorithm

Muhammad Taaha Tariq

August 2025

Introduction

Graphs are widely used to model real-world systems such as social networks, communication channels, and dependency structures. In directed graphs, cycles are particularly significant, and analyzing them through Strongly Connected Components (SCCs) provides valuable insight into the graph’s structure.

An SCC is defined as a subset of nodes in which every node is reachable from every other node within the same subset. Identifying these components is important in applications like deadlock detection, dependency analysis, and compiler optimization.

Among the most efficient methods for this task is Tarjan’s Algorithm, which leverages Depth-First Search (DFS) along with discovery and low-link values to compute SCCs in linear time. This article explains the concept of SCCs and illustrates Tarjan’s Algorithm step by step with examples.

But before diving right into the algorithm, here's a brief recap of the associated concepts.

Graph

A graph is a mathematical structure, particularly in graph theory, consisting of vertices(nodes) and edges that interlink the nodes with each other. In the context of computer science, however, a graph refers to a data structure whose vertices represent some kind of entity(it may be a network node or some data) that is linked to other vertices using connection links(edges).

It consists of two sets:

vertices\mathbf{V} = { v \;|\; \text{set of all vertices} }

edges\mathbf{E} = { e \; |\; \text{set of all the edges}}

Pictorially, it is depicted as circles connected by lines or arrows for different types of graphs.

Two nodes are said to be adjacent if they have an interconnecting edge between them. Adjacency simplifies the concept of interconnection by considering only the nodes adjacent to a given node. Given the above graph, we see that the adjacency list of node A is:

$C][\text{B}, \; \text{C}]$

Furthermore, edges can be directed or undirected. A directed edge represents a unidirectional connection between the two nodes wherein we can only move from one node to the other but not in the other direction, and is commonly depicted with a pointed arrow.

An undirected edge, on the other hand, represents a bidirectional connection between the two nodes.

Based on the nature of the edges between the nodes of a graph, there are two types of graphs that are commonly used in computer science: undirected graphs and directed graphs.

Strongly Connected Components

A strongly connected component of a directed graph is a maximal subgraph where each vertex(node) is mutually reachable.

A subgraph refers to a portion of a graph, or more formally, a subset of the vertex set. The maximality condition refers to the fact that the subgraph cannot be extended while maintaining mutual reachability.

The strongly connected components, therefore, partition the graph into disjoint subgraphs.

Depth-first Search

Depth-first Search is a traversal algorithm that traverses the graph recursively. The important thing to note is that it traverses the graph as a spanning tree.

A spanning tree of a connected graph connects all the nodes of the graph using the minimum number of edges and contains no cycles. Since there are many spanning trees of a graph, the DFS traversal order is not unique.

Considering the graph in figure 1 and starting at A, one possible spanning tree is:

The DFS traversal that produces this spanning tree is as follows:

Start at A.
Recursively, call the routine for B. Then, for D and finally for C.
Then, we backtrack to A.

But, during the traversal, we need to keep track of already visited nodes to prevent indefinite behavior because of cycles, which can be achieved by using an array.

Some additional concepts

DFS spanning trees have two kinds of edges: tree edges and back edges.

Back edges relate a tree node to its ancestor in the traversal order.
Tree edges take us from the parent node to its children.

However, the two most important concepts responsible for this algorithm's efficiency are discovery time and low values.

Discovery time is the time it takes for the DFS to reach a node.
Low values indicate the smallest discovery time reachable from a node. Low values less than a node's discovery time indicate a back edge (a cycle).

Tarjan's algorithm for directed graphs

Tarjan's algorithm is used to find the Strongly Connected Components(SCCs) of a directed graph.

Algorithm

Start at any vertex and assign it a discovery time and a low value of 0.
Iterate over its adjacent nodes, and we push them onto a stack to keep track of the order in which they were traversed, which is essential to correctly updating the low values and identifying potential SSCs, and for the unvisited nodes, recursively call DFS.
For each subsequent node:
- If the adjacent node has already been visited (back edge), update: $\min(low[u], \; disc[v])$
- If the adjacent node has not been visited yet, call DFS and on backtracking, update: $\min(low[u], \; low[v])$
SCC identification: If
$l o w [u] = d i sc [u]$
, then u is the root of an SCC. Pop nodes from the stack until u is popped.

Tarjan's algorithm for undirected graphs

A slightly modified version of Tarjan's algorithm is used for undirected graphs to find the bridges and articulation points.

Algorithm

Start at any vertex and assign it a discovery time and a low value of 0.
Iterate over adjacent nodes, calling DFS with the parent node.
For each node:
- If the adjacent node is the parent, skip.
- If already visited, update: $\min(low[u], \; disc[v])$
- Otherwise, DFS recursively and backtrack update: $\min(low[u], \; low[v])$
Bridge check: If
$l o w [u] > d i sc [v]$
, then (u, v) is a bridge.
Articulation point check: If
$d i sc [u] <= l o w [v]$
, then u is an articulation point (except the root).

Note: In undirected graphs, we skip the parent node because otherwise every parent-child edge looks like a bridge.

Conclusion

The importance of graphs for computer networks and, in general, for computers cannot be overemphasized, and as such, graphs arise in many different applications, and with them arises the need to efficiently work with them on a large scale something that is supplemented by the development of new and more efficient algorithms, one example of such an algorithm is the Tarjan's algorithm which partitions the graph in linear time complexity O(V + E).

References

R. E. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2), 146–160, 1972. doi:10.1137/0201010.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009.
GeeksforGeeks. Tarjan’s Algorithm to Find Strongly Connected Components. Accessed: Aug 2025.