Eulerian Path Check

Determine whether an undirected graph has a trail that uses every edge exactly once.

graph eulerian degree connectivity

Write a function `has_eulerian_path(n, edges)` that determines whether an undirected graph with vertices numbered 0 to n-1 has an Eulerian path. An Eulerian path is a trail that visits every edge exactly once. The graph is simple, meaning it has no self-loops and no multiple edges. But the input may contain duplicate edges; treat duplicates as separate edges (multigraph). For example, two parallel edges between the same pair of vertices count as distinct edges.

To have an Eulerian path, all vertices with non-zero degree must belong to a single connected component, and the number of vertices with odd degree must be either 0 or 2. The empty graph (no edges) always has an Eulerian path.

Return `True` if an Eulerian path exists, and `False` otherwise.

**Input**
- `n`: integer, number of vertices (0 <= n <= 10^5).
- `edges`: list of tuples (u, v) representing undirected edges. 0 <= u, v < n, u != v.

**Output**
- Boolean: `True` if the graph has an Eulerian path, else `False`.

**Function signature**
```python
def has_eulerian_path(n: int, edges: list[tuple[int, int]]) -> bool:
```

Constraints

0 <= n <= 10^5, 0 <= len(edges) <= 10^5. The graph may have parallel edges (duplicate pairs) but no self-loops. Time limit: O(n + m) expected.

Example

>>> has_eulerian_path(4, [(0,1),(1,2),(2,3),(3,0)])
True
>>> has_eulerian_path(3, [(0,1),(1,2),(0,2)])
True
>>> has_eulerian_path(3, [(0,1),(1,2)])
True
>>> has_eulerian_path(0, [])
True

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Count the degree of each vertex, counting each occurrence of an edge separately.

Check that the number of odd-degree vertices is 0 or 2.

Use BFS/DFS to verify connectivity among vertices with non-zero degree, treating parallel edges normally.

The empty graph (no edges) always has an Eulerian path.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.