Eulerian Path and Circuit — Hierholzer's Algorithm

Euler's solution to the Seven Bridges of Königsberg in 1736 is considered the founding paper of graph theory and one of the earliest proofs in discrete mathematics. The question was whether a walker could cross all seven bridges of Königsberg exactly once and return to the start. Euler proved it was impossible — and in doing so invented the mathematical framework we now call graph theory.

The algorithm itself (Hierholzer's, 1873) is elegant: find a cycle, find a node on the cycle with unused edges, extend. The linear time O(E) complexity is achievable because each edge is traversed exactly once. In bioinformatics, Eulerian paths in de Bruijn graphs are how genome assemblers reconstruct DNA sequences from millions of short reads — perhaps the most important modern application of 230-year-old graph theory.

Eulerian Path and Circuit — The Edge-Traversal Problem Solved

An Eulerian path is a trail in a finite graph that visits every edge exactly once. An Eulerian circuit is a path that starts and ends on the same vertex. The core mechanic: you can traverse every edge without repetition. For an undirected graph, an Eulerian circuit exists iff every vertex has even degree and the graph is connected (ignoring isolated vertices). For a directed graph, every vertex must have equal in-degree and out-degree, and the underlying undirected graph must be connected. In practice, the condition is O(V+E) to check — you count degrees, then verify connectivity via DFS or union-find.

Hierholzer's algorithm constructs the circuit in O(E) time by walking edges and splicing cycles. Start at any vertex with non-zero degree (or the correct start for a path), follow unused edges until you get stuck, then backtrack to a vertex with remaining edges and repeat. The algorithm works because each time you close a cycle, you merge it into the growing trail. The key property: you never need to backtrack more than once per edge, making it optimal for dense graphs.

Use this when you need to trace a route that covers every connection exactly once — network packet routing, DNA fragment assembly, or garbage truck route planning. It matters because brute-force search is exponential, but Hierholzer gives a linear-time guarantee. In real systems, the graph must be pre-validated for Eulerian properties; otherwise, you'll get a partial trail and no indication of failure.

Existence Conditions

Undirected graph: - Eulerian circuit exists ↔ graph is connected AND every vertex has even degree - Eulerian path exists ↔ graph is connected AND exactly 0 or 2 vertices have odd degree (path goes from one odd-degree vertex to the other)

Directed graph: - Eulerian circuit exists ↔ strongly connected AND every vertex: in-degree = out-degree - Eulerian path exists ↔ weakly connected AND at most one vertex has out-degree - in-degree = 1 (start) AND at most one vertex has in-degree - out-degree = 1 (end)

from collections import defaultdict

def has_eulerian_circuit(adj: dict) -> bool:
    # All vertices must have even degree
    return all(len(neighbours) % 2 == 0 for neighbours in adj.values())

def has_eulerian_path(adj: dict) -> bool:
    odd_degree = sum(1 for v in adj if len(adj[v]) % 2 != 0)
    return odd_degree == 0 or odd_degree == 2

# Königsberg bridges — all 4 vertices have odd degree
konigsberg = {'A':['B','B','D'], 'B':['A','A','C','C'], 'C':['B','B','D'], 'D':['A','C']}
print(has_eulerian_circuit(konigsberg))  # False
print(has_eulerian_path(konigsberg))     # False — no Eulerian path!

Hierholzer's Algorithm — O(E)

1. Start at any vertex (or an odd-degree vertex for Eulerian path)
2. Walk randomly, never reusing edges, until stuck
3. If stuck at start: done if all edges used; otherwise, find a vertex on the current circuit with unused edges
4. Insert a new circuit from that vertex into the main circuit
5. Repeat until all edges are used

from collections import defaultdict

def eulerian_circuit(adj_input: dict) -> list:
    """
    Find Eulerian circuit using Hierholzer's algorithm.
    adj_input: {vertex: [neighbours]} — will be modified
    """
    adj = defaultdict(list)
    for u, neighbours in adj_input.items():
        adj[u].extend(neighbours)

    # Check all vertices have even degree
    if not all(len(adj[v]) % 2 == 0 for v in adj):
        return []  # No Eulerian circuit

    start = next(iter(adj))
    stack = [start]
    circuit = []

    while stack:
        v = stack[-1]
        if adj[v]:
            u = adj[v].pop()
            adj[u].remove(v)  # remove reverse edge for undirected
            stack.append(u)
        else:
            circuit.append(stack.pop())

    return circuit[::-1]

adj = {0:[1,2], 1:[0,2], 2:[0,1]}
print(eulerian_circuit(adj))  # [0, 1, 2, 0] (triangle)

The Seven Bridges of Königsberg

Euler proved in 1736 that the city of Königsberg (now Kaliningrad) has no Eulerian path. The city has 4 landmasses connected by 7 bridges. Each landmass has an odd number of bridges (3, 5, 3, 3). For an Eulerian path, at most 2 vertices can have odd degree. With 4 odd-degree vertices, neither an Eulerian path nor circuit exists.

This is the founding problem of graph theory.

Applications

• DNA fragment assembly: Eulerian path in de Bruijn graphs reassembles genome sequences
• Route planning: Postman problem — minimum edges to add to make graph Eulerian
• Circuit design: Drawing PCB traces without lifting the pen
• Puzzle solving: Draw-without-lifting-pen puzzles

Directed Eulerian Paths and Circuits

The algorithm for directed graphs is similar to undirected, but when traversing, you only pop an outgoing edge from the current vertex's adjacency list — you don't remove reverse edges because they don't exist as separate entries. The code is slightly simpler: no adj[u].remove(v) step.

from collections import defaultdict

def eulerian_circuit_directed(adj_input: dict) -> list:
    """
    Find Eulerian circuit in directed graph.
    adj_input: {vertex: [outgoing neighbours]}
    """
    adj = defaultdict(list)
    for u, neighbours in adj_input.items():
        adj[u].extend(neighbours)
    
    # Check in-degree == out-degree (requires degree computation outside this snippet)
    # For simplicity, assume condition met
    start = next(iter(adj))
    stack = [start]
    circuit = []
    while stack:
        v = stack[-1]
        if adj[v]:
            u = adj[v].pop()
            stack.append(u)
        else:
            circuit.append(stack.pop())
    return circuit[::-1]

digraph = {0:[1,2], 1:[2], 2:[0]}
print(eulerian_circuit_directed(digraph))  # [0,1,2,0]

Performance and Implementation Trade-offs

Hierholzer's algorithm is O(E) time and O(V+E) space (to store adjacency lists). The iterative stack version uses O(E) additional space in the worst case for the stack. The recursive version uses O(E) call stack memory, which can be prohibitive for large graphs.

Important: The algorithm modifies the adjacency list — each edge is removed when traversed. This means you must copy the input if you need the original graph later. For read-heavy applications, consider a read-only approach: mark edges as used instead of deleting them. That increases memory but preserves the graph.

C++ Implementation of Hierholzer's Algorithm

While the Python version is great for prototyping, C++ is often used in performance-critical bioinformatics pipelines. The implementation below demonstrates Hierholzer's algorithm for both undirected and directed graphs. Key differences from Python: you must manage edge removal carefully — for undirected graphs, we use std::multiset to allow multiple edges and erase a single element using an iterator. For directed graphs, we only pop from the outgoing list.

Undirected Version: Uses std::unordered_map<int, std::multiset<int>> to store adjacency. When traversing edge u→v, we remove v from adj[u] and u from adj[v] (erase one iterator each).

Directed Version: Uses std::unordered_map<int, std::vector<int>> and pops from the back (which is O(1) amortized). No reverse edge removal needed.

The iterative stack avoids recursion depth issues. The circuit is built in reverse and returned in correct order.

#include <bits/stdc++.h>
using namespace std;

// Undirected Hierholzer
vector<int> eulerian_circuit_undirected(unordered_map<int, multiset<int>>& adj) {
    for (auto& [v, neighbours] : adj) {
        if (neighbours.size() % 2 != 0) return {}; // not Eulerian
    }
    int start = adj.begin()->first;
    stack<int> st;
    st.push(start);
    vector<int> circuit;
    while (!st.empty()) {
        int v = st.top();
        auto& neighbors = adj[v];
        if (!neighbors.empty()) {
            auto it = neighbors.begin();
            int u = *it;
            neighbors.erase(it);           // remove from v
            adj[u].erase(adj[u].find(v));  // remove reverse from u
            st.push(u);
        } else {
            circuit.push_back(v);
            st.pop();
        }
    }
    reverse(circuit.begin(), circuit.end());
    return circuit;
}

// Directed Hierholzer
vector<int> eulerian_circuit_directed(unordered_map<int, vector<int>>& adj) {
    // Assume in-degree == out-degree verified separately
    int start = adj.begin()->first;
    stack<int> st;
    st.push(start);
    vector<int> circuit;
    while (!st.empty()) {
        int v = st.top();
        auto& neighbors = adj[v];
        if (!neighbors.empty()) {
            int u = neighbors.back();
            neighbors.pop_back();
            st.push(u);
        } else {
            circuit.push_back(v);
            st.pop();
        }
    }
    reverse(circuit.begin(), circuit.end());
    return circuit;
}

Fleury's Algorithm: A Safe-Bridge Alternative

Before Hierholzer, Fleury (1883) proposed a simpler greedy algorithm: start from an odd-degree vertex (if one exists), and at each step, choose an edge that is not a bridge unless no other choice exists. A bridge is an edge whose removal disconnects the graph. By avoiding bridges, you ensure you don't cut off unused edges from the remaining subgraph.

Algorithm: 1. Start at a vertex (odd-degree if path, any if circuit). 2. For each adjacent edge, test if it's a bridge using DFS. If it's a bridge and there are other non-bridge edges, skip it. 3. Traverse the chosen edge, remove it, and move to the next vertex. 4. Repeat until all edges are used.

Complexity: O(E²) because for each edge you test bridges with a DFS (O(E)). This makes it impractical for large graphs. Hierholzer's O(E) is strictly better.

Why learn Fleury? It provides a different perspective — the concept of safe edges (non-bridges) is useful in network reliability. Also, some interview questions test understanding of bridge detection in this context.

Contrast Table:

Starting Vertex Selection for Eulerian Paths

For an Eulerian circuit, you can start at any vertex that has edges (degree > 0). The algorithm will return a circuit covering all edges. However, for an Eulerian path (not circuit), the starting vertex must be one of the two odd-degree vertices (if exactly two exist). If all vertices have even degree, the graph has a circuit, so any vertex works for both circuit and path.

Why? In an Eulerian path, the start vertex must have one more outgoing than incoming (or degree odd in undirected) because the path ends elsewhere. The vertex with odd degree (or out-in = 1) is the only one that can serve as start if you want to use all edges.

How to choose in code: 1. Compute degrees (in/out for directed, just degree for undirected). 2. If exactly two vertices have odd degree (undirected) or exactly one source (out-in=1) and one sink (in-out=1), pick the odd-degree/source vertex as start. 3. If all even (or in=out), pick any vertex — the graph is Eulerian. 4. If no such vertex exists, no Eulerian path exists; return [] before running algorithm.

Edge case: For directed graphs with an Eulerian circuit, you can start at any vertex. But if an Eulerian path exists, you must start at the source vertex. The algorithm still works: if you start at the wrong vertex, you might get a circuit that doesn't cover all edges, or you'll get stuck early.

def find_start_vertex_undirected(adj: dict) -> int:
    odd_vertices = [v for v, neigh in adj.items() if len(neigh) % 2 != 0]
    if len(odd_vertices) == 0:
        return next(iter(adj))  # circuit, any vertex
    elif len(odd_vertices) == 2:
        return odd_vertices[0]  # start at one of the two odd-degree vertices
    else:
        return None  # no Eulerian path

def find_start_vertex_directed(in_deg: dict, out_deg: dict) -> int:
    start = [v for v in out_deg if out_deg[v] - in_deg.get(v,0) == 1]
    end = [v for v in in_deg if in_deg[v] - out_deg.get(v,0) == 1]
    if len(start) == 1 and len(end) == 1:
        return start[0]
    elif len(start) == 0 and len(end) == 0:
        return next(iter(out_deg))  # circuit
    else:
        return None

Advantages and Disadvantages of Hierholzer's Algorithm

Hierholzer's algorithm is the standard for finding Eulerian paths and circuits. Here are its key strengths and weaknesses:

When to avoid Hierholzer: - If your graph is dynamic (edges added/removed frequently), the static algorithm must be re-run. - If you need to find all Eulerian circuits (enumeration is #P-complete), you need different approaches. - For graphs that are Hamiltonian-like (vertex coverage), Hierholzer is irrelevant.

When it shines: - In any application where you need one Eulerian traversal: street sweeping, DNA assembly, network troubleshooting.

The Chinese Postman Problem (Route Inspection)

The Chinese Postman Problem (also called Route Inspection Problem) asks: find the shortest closed walk that visits every edge at least once and returns to the start. If the graph is Eulerian (all even degrees), the answer is simply the sum of edge weights along an Eulerian circuit. If not, you must duplicate some edges (add traversals) to make all vertices even degree, then find an Eulerian circuit on the augmented graph.

How it works: 1. Identify vertices with odd degree (they come in pairs). 2. Compute shortest paths between all pairs of odd-degree vertices (using Floyd-Warshall or Dijkstra from each). 3. Solve a minimum-weight perfect matching on the odd-degree vertices: pair them up so that the sum of shortest path distances is minimized. This pairing tells you which edges to traverse twice (or add as virtual edges). 4. Add those shortest paths to the graph (duplicating edges), then find an Eulerian circuit on the resulting Eulerian graph.

Real-world applications: - Mail delivery: Postman needs to walk every street at least once; minimize total distance. - Snow plowing: Plow every road; duplicates add extra passes. - Street sweeping: Same idea. - Network inspection: Inspect every cable/fiber segment; extra traversals add time.

Complexity: O(V³) with Floyd-Warshall, plus O(k³) for matching where k = number of odd-degree vertices (usually small). For general graphs, this is polynomial and practical for city-scale road networks.

import itertools
from collections import defaultdict

def chinese_postman_cost(adj: dict) -> int:
    # Step 1: find odd-degree vertices
    odd = [v for v, neigh in adj.items() if len(neigh) % 2 != 0]
    if len(odd) == 0:
        return sum(weight for _, _, weight in edges(adj))  # already Eulerian
    
    # Step 2: compute all-pairs shortest paths (Floyd-Warshall)
    vertices = list(adj.keys())
    dist = {v: {u: float('inf') for u in vertices} for v in vertices}
    for v in vertices:
        dist[v][v] = 0
        for u, w in adj[v]:  # assume adj[v] is list of (neighbor, weight)
            dist[v][u] = w
    for k in vertices:
        for i in vertices:
            for j in vertices:
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    # Step 3: minimum weight perfect matching on odd vertices (brute force for small k)
    k = len(odd)
    min_extra = float('inf')
    for perm in itertools.permutations(odd):
        if perm[0] > perm[1]:  # avoid symmetric
            continue
        pairs = list(zip(perm[::2], perm[1::2]))
        total = sum(dist[u][v] for u,v in pairs)
        min_extra = min(min_extra, total)
    return sum(w for _, _, w in edges(adj)) + min_extra

Practice Problems

Sharpen your Eulerian path/circuit skills with these curated problems. They range from direct algorithm implementation to complex variants requiring existence checks and optimizations.

1. LeetCode 332 — Reconstruct Itinerary (Medium)
2. - Given a list of airline tickets (from, to), find an itinerary that uses all tickets exactly once (Eulerian path in a directed graph).
3. - [https://leetcode.com/problems/reconstruct-itinerary/](https://leetcode.com/problems/reconstruct-itinerary/)
4. - Hint: Use Hierholzer with lexical ordering; the graph is guaranteed to have an Eulerian path.
5. CSES — Eulerian Path (Easy)
6. - Directed graph; check existence and output one Eulerian path if it exists.
7. - [https://cses.fi/problemset/task/1699](https://cses.fi/problemset/task/1699)
8. - Straightforward implementation of Hierholzer.
9. CSES — Eulerian Circuit (Easy)
10. - Same as above but circuit.
11. - [https://cses.fi/problemset/task/1698](https://cses.fi/problemset/task/1698)
12. Codeforces — C. Eulerian Path (Medium)
13. - Classic: check if Eulerian path exists, print it.
14. - [https://codeforces.com/problemset/problem/1188/A2](https://codeforces.com/problemset/problem/1188/A2) (actually this is about tree degrees; look for problem 1188B? Not exact. Use: CF 1188A1? Let's correct: CF 500E? We'll point to a known one: CF 25C? I'll provide a more reliable: Open Kattis — Eulerian Path)
15. - Let's use: Open Kattis — Eulerianpath [https://open.kattis.com/problems/eulerianpath](https://open.kattis.com/problems/eulerianpath) (undirected, check existence and output).
16. Codeforces — 723E: One-Way Reform (Hard)
17. - Given an undirected graph, orient edges so that the number of vertices with equal in/out degree is maximized.
18. - [https://codeforces.com/problemset/problem/723/E](https://codeforces.com/problemset/problem/723/E)
19. - Requires understanding of Eulerian graph conditions and matching.
20. SPOJ — WORDS1: Play on Words (Easy)
21. - Given words, determine if you can chain them so last letter of one matches first letter of the next (Eulerian path in a graph of first/last letters).
22. - [https://www.spoj.com/problems/WORDS1/](https://www.spoj.com/problems/WORDS1/)
23. UVA — 10054: The Necklace (Medium)
24. - Given beads with colors on each side, find a necklace arrangement that uses all beads (Eulerian circuit in multigraph).
25. - [https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=995](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=995)

Tip: Start with LeetCode 332 and CSES problems to get comfortable with Hierholzer's algorithm in both directed and undirected settings. Then move to harder problems like Codeforces 723E for deeper insights into degree constraints.

Why Your Git Commit Log Is a Eulerian Trail Wrapper

You've been writing Eulerian path logic every day without knowing it. Every time you rebase a feature branch with 30 commits, you're solving a smaller instance of the same edge-traversal problem. Your commit DAG is a directed graph. Each commit is a vertex. Each parent-child relationship is an edge. A clean rebase that linearizes history? That's an Eulerian trail covering every connection exactly once.

The real nightmare starts when you have merge commits that create divergence. Your history graph gets vertices with odd out-degree. Suddenly you're dealing with the equivalent of an Eulerian path starting at the first commit and ending at the last. Git doesn't tell you this because it doesn't need to — it just uses topological sort. But when you're writing a custom git-lite tool for your CI pipeline, understanding this isomorphism saves you three days of debugging.

Why does this matter? Because your commit graph traversal algorithm either works O(E) or it crashes on repos with 10,000+ commits. Hierholzer's edge-hopping is exactly the same logic as walking a commit chain without revisiting parent links.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class CommitTrailValidator {
    // Validates rebase history as Eulerian path
    public static List<String> linearizeCommits(List<String[]> edges) {
        // Build adjacency: commit hash -> children
        Map<String, List<String>> graph = new HashMap<>();
        Map<String, Integer> inDegree = new HashMap<>();
        
        for (String[] edge : edges) {
            String parent = edge[0], child = edge[1];
            graph.computeIfAbsent(parent, k -> new ArrayList<>()).add(child);
            inDegree.merge(child, 1, Integer::sum);
            inDegree.putIfAbsent(parent, 0);
        }
        
        // Find root: exactly one vertex with inDegree 0
        String root = inDegree.entrySet().stream()
            .filter(e -> e.getValue() == 0)
            .map(Map.Entry::getKey)
            .findFirst()
            .orElseThrow(() -> new RuntimeException("Cycle or fork detected"));
        
        return Hierholzer.traverse(graph, root);
    }
}

The Star History Graph Is a Eulerian Path You're Ignoring

Look at any popular repo's star history graph. See that upward curve? That's a directed graph of events over time. Each star event is an edge from the user vertex to the repo vertex. You can traverse that entire timeline without backtracking — that's exactly what Hierholzer's algorithm does.

Here's where juniors get burned: They try to query star history with nested loops over user accounts. That's O(users * stars). Production repos like TensorFlow have 180k+ stars. Your query implodes at 50k. The fix? Treat the star timeline as an Eulerian circuit. You only need to touch each edge (star event) once. Build an adjacency list of events sorted by timestamp, then walk it linearly.

GitHub doesn't expose this because their API paginates. But when you're building internal tooling to analyze community growth patterns, this traversal pattern prevents timeout errors. The graph structure is literally a collection of paths from every starrer to every starrer — symmetric edges forming an even-degree graph. That's your green light for circuit traversal.

// io.thecodeforge — dsa tutorial

import java.util.*;
import java.time.*;

public class StarTrailAnalyzer {
    public static List<StarEvent> linearStarHistory(List<StarEvent> events) {
        // Build adjacency: userId -> list of star events (edges)
        Map<String, Deque<StarEvent>> adjacency = new HashMap<>();
        for (StarEvent e : events) {
            adjacency.computeIfAbsent(e.userId, k -> new ArrayDeque<>()).add(e);
        }
        
        // Find the first event by timestamp — start vertex
        StarEvent start = events.stream()
            .min(Comparator.comparing(e -> e.timestamp))
            .orElseThrow();
        
        return Hierholzer.eulerianWalk(adjacency, start.userId);
    }
    
    record StarEvent(String userId, String repoId, Instant timestamp) {}
}

Fleury's Algorithm Will Save Your Network Routing Stack (Don't Use Dijkstra Here)

You're building a network route validator for your mesh topology service. Every switch (vertex) must be visited exactly once per maintenance cycle. Juniors reach for Dijkstra or DFS. Both are wrong. You don't need shortest path — you need an edge-traversal path that doesn't burn bridges.

Fleury's algorithm exists because sometimes you can't afford backtracking. In network routing, "burning a bridge" means taking a path that disconnects the remaining network. That's a production outage. Fleury's greedy approach checks each candidate edge: "Does removing this edge leave the graph connected?" If no, skip it. It's O(E²) but for sparse networks (think <5000 edges), it beats Hierholzer's complexity because Hierholzer requires full graph reconstruction on reconnect.

Real talk: Don't use Fleury for game maps or social graphs. Those are dense. Use it for network topologies, circuit board traces, or any physical routing where edges represent actual cables. One wrong edge removal and you're dispatching a field tech. Test your graph density first. Sparse graphs (< 5k edges) are Fleury territory. Everything else, go Hierholzer.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class NetworkBridgeValidator {
    public static List<String> routeWithoutBridges(Map<String, List<String>> graph) {
        // Copy graph — we mutate during traversal
        Map<String, List<String>> mutable = deepCopy(graph);
        List<String> path = new ArrayList<>();
        
        String current = findStartVertex(mutable);
        while (hasEdges(mutable, current)) {
            path.add(current);
            
            // Fleury's critical check: skip edge if it's a bridge
            for (String neighbor : new ArrayList<>(mutable.get(current))) {
                if (isBridge(mutable, current, neighbor)) continue;
                removeEdge(mutable, current, neighbor);
                current = neighbor;
                break;
            }
        }
        path.add(current);
        return path;
    }
}

Incidence

In graph theory, incidence describes the relationship between vertices and edges. For Eulerian Path/Circuit problems, tracking edge incidence is critical: each vertex's incident edges determine whether it can serve as a start or end node. In directed graphs, the incidence count splits into in-degree (edges entering) and out-degree (edges leaving). For an Eulerian Circuit, every vertex must have equal in-degree and out-degree. For an Eulerian Path, exactly one vertex can have out-degree = in-degree + 1 (start), one vertex with in-degree = out-degree + 1 (end), and all others balanced. In undirected graphs, vertices of odd degree are incident to an odd number of edges; an Eulerian Circuit requires zero odd-degree vertices, while a Path requires exactly two. Failing to verify incidence before running algorithms like Hierholzer’s will produce incorrect trails or infinite loops. Always compute degree arrays first.

// io.thecodeforge — dsa tutorial
// Check vertex incidence for Eulerian Path in directed graph
import java.util.*;

public class IncidenceCheck {
    static boolean hasEulerianPath(int n, int[][] edges) {
        int[] inDeg = new int[n], outDeg = new int[n];
        for (int[] e : edges) {
            outDeg[e[0]]++;
            inDeg[e[1]]++;
        }
        int start = 0, end = 0;
        for (int i = 0; i < n; i++) {
            if (outDeg[i] - inDeg[i] == 1) start++;
            else if (inDeg[i] - outDeg[i] == 1) end++;
            else if (outDeg[i] != inDeg[i]) return false;
        }
        return (start == 0 && end == 0) || (start == 1 && end == 1);
    }
    public static void main(String[] args) {
        int[][] edges = {{0,1},{1,2},{2,0}};
        System.out.println(hasEulerianPath(3, edges)); // true
    }
}

Conclusion

Eulerian Path and Circuit problems are fundamental to graph traversal with real-world applications in network routing, DNA assembly, and route optimization. The choice between Hierholzer's Algorithm (O(E) time, adjacency list) and Fleury's Algorithm (O(E²) due to bridge detection) depends on graph size and edge constraints. The key insight is incidence: every vertex's degree parity dictates whether an Eulerian structure exists. For large graphs, Hierholzer's dominates in performance; for small graphs with explicit bridge requirements, Fleury's offers simplicity. The Chinese Postman Problem extends Eulerian paths to weighted edges, connecting this theory to practical route inspection. Remember: Eulerian structures exist only when vertex degrees satisfy precise incidence rules. Mastering these algorithms enables elegant solutions to routing and traversal challenges. Always validate input graphs against incidence conditions first — this catches errors early and guides algorithm selection. For further study, explore dynamic Eulerian updates in streaming graphs.

// io.thecodeforge — dsa tutorial
// Final Eulerian Path demo using Hierholzer
import java.util.*;

public class EulerianDemo {
    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(0, new ArrayList<>(List.of(1, 2)));
        graph.put(1, new ArrayList<>(List.of(2)));
        graph.put(2, new ArrayList<>(List.of(0, 1)));
        
        Deque<Integer> stack = new ArrayDeque<>();
        List<Integer> path = new ArrayList<>();
        stack.push(0);
        while (!stack.isEmpty()) {
            int v = stack.peek();
            if (graph.get(v).isEmpty()) {
                path.add(stack.pop());
            } else {
                int u = graph.get(v).remove(0);
                stack.push(u);
            }
        }
        Collections.reverse(path);
        System.out.println(path); // [0, 1, 2, 0, 2, 1, 0]? depends
    }
}