Log inSign up
hardGeeksforGeeksNot Started

Eulerian Path and Circuit

Given an undirected connected graph with V vertices and an adjacency list adj, determine whether the graph contains an Eulerian Circuit, an Eulerian Path, or neither.

Graph
Solve on GeeksforGeeks
Lesson

Problem Statement

### Problem Statement

Given an undirected graph with V vertices numbered 0 to V - 1 and an adjacency list adj.

An Eulerian Path is a trail in a finite graph that visits every edge exactly once. An Eulerian Circuit (or Euler Tour) is an Eulerian Path that starts and ends on the same vertex.

Determine the Eulerian nature of the graph and return: - 2 if the graph contains an Eulerian Circuit. - 1 if the graph contains an Eulerian Path (but not an Eulerian Circuit). - 0 if the graph is Neither (non-Eulerian).

---

### Examples

Example 1 (Eulerian Circuit): ``text Input: V = 5, adj = [[1, 2], [0, 2], [0, 1, 3, 4], [2, 4], [2, 3]] Output: 2 Explanation: Vertex degrees: deg(0)=2, deg(1)=2, deg(2)=4, deg(3)=2, deg(4)=2. All vertices with non-zero degree have EVEN degrees and belong to a single connected component. Thus, the graph has an Eulerian Circuit.

Example 2 (Eulerian Path): ``text Input: V = 4, adj = [[1, 2], [0, 2, 3], [0, 1], [1]] Output: 1 Explanation: Degrees: deg(0)=2, deg(1)=3 (odd), deg(2)=2, deg(3)=1 (odd). Exactly two vertices have ODD degree (vertices 1 and 3). Thus, the graph has an Eulerian Path starting at 1 and ending at 3 (or vice versa).

Example 3 (Neither): ``text Input: V = 4, adj = [[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]] Output: 0 Explanation: More than two vertices have odd degrees.

---

### Constraints - 1 <= V <= 10^5 - 0 <= adj[i].length <= V - Undirected graph without parallel edges or self-loops.

Constraints:

  • 1 <= V <= 105
  • 0 <= E <= 2 * 105
  • 0-indexed undirected graph

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Formulate Euler's Theorem on vertex degree parity and connectivity.
  • Handle isolated zero-degree vertices correctly during connectivity checks.
  • Differentiate between Eulerian Trails, Eulerian Circuits, and Hamiltonian paths.
  • Implement the complete decision framework in C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Visiting every road or edge in a city exactly once (Chinese Postman / Snowplow problem).
  • Reconstructing DNA sequences from overlapping k-mers (De Bruijn graphs).
  • Tracing continuous figures without lifting the pencil.

Algorithmic Decision Tree:

  • If asking to construct the path -> Hierholzer's algorithm in O(V + E).
  • If asking existence (Circuit / Path / Neither) -> Count odd-degree vertices + DFS connectivity check in O(V + E).

Connected Patterns:

Fleury's AlgorithmReconstruct ItineraryHierholzer's Algorithm

1. Backtracking Hamiltonian-Dual Edge Trail Search

Intuition

Use backtracking to find an edge-disjoint walk of length E visiting every edge once.

Algorithm

  1. From each candidate starting vertex, attempt a recursive DFS.
  2. Mark each edge as used when crossed.
  3. If the path length reaches total edges E, check if start == end for circuit.
  4. Backtrack and reset used edge flags.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <map>
4
5using namespace std;
6
7bool dfs(int u, int count, int totalE, vector<vector<int>>& adj, map<pair<int, int>, int>& edgeCount, int startNode, bool& isCircuit) {
8 if (count == totalE) {
9 if (u == startNode) isCircuit = true;
10 return true;
11 }
12
13 for (int v : adj[u]) {
14 pair<int, int> e = {min(u, v), max(u, v)};
15 if (edgeCount[e] > 0) {
16 edgeCount[e]--;
17 if (dfs(v, count + 1, totalE, adj, edgeCount, startNode, isCircuit)) {
18 return true;
19 }
20 edgeCount[e]++;
21 }
22 }
23 return false;
24}
25
26int isEulerianBruteForce(int V, vector<vector<int>>& adj) {
27 map<pair<int, int>, int> edgeCount;
28 int totalE = 0;
29 for (int u = 0; u < V; ++u) {
30 for (int v : adj[u]) {
31 if (u < v) {
32 edgeCount[{u, v}]++;
33 totalE++;
34 }
35 }
36 }
37
38 if (totalE == 0) return 2;
39
40 for (int i = 0; i < V; ++i) {
41 bool isCircuit = false;
42 auto copyEdges = edgeCount;
43 if (dfs(i, 0, totalE, adj, copyEdges, i, isCircuit)) {
44 return isCircuit ? 2 : 1;
45 }
46 }
47 return 0;
48}
49
50int main() {
51 int V = 5;
52 vector<vector<int>> adj = {{1, 2}, {0, 2}, {0, 1, 3, 4}, {2, 4}, {2, 3}};
53 cout << "Eulerian Status: " << isEulerianBruteForce(V, adj) << endl;
54 return 0;
55}

Time & Space Complexity

  • Time complexity: O(V!)
  • Space complexity: O(E)

2. Fleury's Greedy Bridge-Avoiding Trail Walk

Intuition

Greedily traverse edges one by one, checking whether each edge is a bridge using DFS. Never burn a bridge unless no alternative exists.

Algorithm

  1. Find valid start node (odd-degree vertex if 2 exist, else any non-zero vertex).
  2. Repeat until all edges consumed:
  3. For each adjacent edge (u, v):
  4. If (u, v) is the sole remaining edge, traverse it.
  5. Otherwise, test if (u, v) is a bridge. If not a bridge, traverse it.
  6. If all E edges crossed, report circuit or path based on endpoint.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6// Simplified Fleury's existence validation
7int isEulerianFleury(int V, const vector<vector<int>>& adj) {
8 int oddCount = 0;
9 int edges = 0;
10 for (int i = 0; i < V; ++i) {
11 if (adj[i].size() % 2 != 0) oddCount++;
12 edges += adj[i].size();
13 }
14 if (edges == 0) return 2;
15 if (oddCount == 0) return 2;
16 if (oddCount == 2) return 1;
17 return 0;
18}
19
20int main() {
21 int V = 5;
22 vector<vector<int>> adj = {{1, 2}, {0, 2}, {0, 1, 3, 4}, {2, 4}, {2, 3}};
23 cout << "Fleury Status: " << isEulerianFleury(V, adj) << endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(E^2)
  • Space complexity: O(V + E)

3. Euler's Theorem Degree Parity & DFS Connectivity (Optimal)

Intuition

Check that all non-zero degree vertices belong to a single connected component using DFS, then count odd-degree vertices. Returns 2 for 0 odds, 1 for 2 odds, and 0 otherwise.

Algorithm

  1. Find first vertex u with adj[u].size() > 0. If no such vertex exists, return 2 (0 edges).
  2. Run DFS from u to mark all visited vertices.
  3. Verify connectivity: if any vertex v has adj[v].size() > 0 and visited[v] == false, return 0 (disconnected edges).
  4. Count vertices with odd degrees:
  5. oddCount = count of i where adj[i].size() % 2 != 0.
  6. If oddCount == 0: return 2 (Eulerian Circuit).
  7. If oddCount == 2: return 1 (Eulerian Path).
  8. Otherwise: return 0 (Neither).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6void dfs(int u, const vector<vector<int>>& adj, vector<bool>& visited) {
7 visited[u] = true;
8 for (int v : adj[u]) {
9 if (!visited[v]) {
10 dfs(v, adj, visited);
11 }
12 }
13}
14
15int isEulerianCircuit(int V, const vector<vector<int>>& adj) {
16 // 1. Find a vertex with degree > 0
17 int startNode = -1;
18 for (int i = 0; i < V; ++i) {
19 if (!adj[i].empty()) {
20 startNode = i;
21 break;
22 }
23 }
24
25 // Graph with 0 edges has an Eulerian circuit vacuously
26 if (startNode == -1) return 2;
27
28 // 2. Check if all non-zero degree vertices are in a single component
29 vector<bool> visited(V, false);
30 dfs(startNode, adj, visited);
31
32 for (int i = 0; i < V; ++i) {
33 if (!adj[i].empty() && !visited[i]) {
34 return 0; // Multiple connected components with edges
35 }
36 }
37
38 // 3. Count odd degree vertices
39 int oddCount = 0;
40 for (int i = 0; i < V; ++i) {
41 if (adj[i].size() % 2 != 0) {
42 oddCount++;
43 }
44 }
45
46 if (oddCount == 0) return 2; // Eulerian Circuit
47 if (oddCount == 2) return 1; // Eulerian Path
48 return 0; // Neither
49}
50
51int main() {
52 int V = 5;
53 vector<vector<int>> adj = {{1, 2}, {0, 2}, {0, 1, 3, 4}, {2, 4}, {2, 3}};
54 cout << "Eulerian Status: " << isEulerianCircuit(V, adj) << endl;
55
56 // Test Eulerian path (2 odd degrees)
57 vector<vector<int>> pathAdj = {{1, 2}, {0, 2, 3}, {0, 1}, {1}};
58 cout << "Path Graph Status: " << isEulerianCircuit(4, pathAdj) << endl;
59 return 0;
60}

Time & Space Complexity

  • Time complexity: O(V + E)
  • Space complexity: O(V)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Backtracking Path SearchO(V!)O(E)Backtrack along edges attempting to form an edge-disjoint walk of length E.Combinatorial path explosion.
2.Fleury's Algorithm (Check bridges during walk)O(E^2)O(V + E)Walk along edges, never crossing a bridge unless no alternative exists.Running Tarjan's bridge check repeatedly.
3.Euler's Parity & Connectivity Check (Optimal)OptimalO(V + E)O(V)Count odd-degree vertices. Check if all vertices with degree > 0 belong to a single DFS component.Single DFS traversal + degree scan.

Common Pitfalls & Crucial Edge Cases

Failing to verify connectivity of non-zero degree vertices

Only checking degree parity without ensuring edges are connected leads to false positives on disjoint cycles.

Checking all V vertices for connectivity

Including degree-0 isolated nodes in the connectivity check causes false negatives.

Inverting 1 and 2 in return values

2 represents Circuit (0 odds), 1 represents Path (2 odds).

Crucial Edge Cases to Validate:

  • Graph with 0 edges (all isolated vertices) — Vacuously an Eulerian Circuit; returns 2.
  • Disconnected components each having edges — Returns 0 (Neither).
  • Star Graph — Center has degree V - 1, leaves have degree 1. If V > 3, more than 2 odd vertices => returns 0.
  • Single edge graph (V = 2, E = 1) — Both endpoints have degree 1 (odd) => Eulerian Path (returns 1).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State Euler's conditions immediately: (1) Connected non-zero degree vertices, (2) Degree parity count.
  2. Connect this problem to real-world applications like the Königsberg Bridge Problem and genome assembly.
  3. Mention Hierholzer's Algorithm as the standard linear O(V + E) algorithm to construct the path if required.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why can an undirected graph NEVER have an odd number of vertices with odd degree (e.g. 1 or 3 odd-degree vertices)?

2.What should the algorithm return if all edges in the graph belong to one component, but there are 10 isolated vertices with degree 0?

Back to DSA Sheet