Eulerian paths and cycles are fundamental concepts in graph theory that help us understand how to traverse all edges in a graph exactly once. Let’s explore these concepts with visual examples and clear explanations.
Basic Definitions
- Eulerian Path: A path that visits every edge in a graph exactly once 2:0
- Eulerian Circuit: A special case of Eulerian path that starts and ends at the same vertex 3:0
Let’s visualize these concepts with a simple example:
flowchart LR subgraph "Eulerian Circuit Example" A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A B --- D end subgraph "Properties" P1["• All vertices have even degree • All vertices are connected • Can start/end at any vertex"] end style A fill:#f9f,stroke:#333,color:#000 style B fill:#f9f,stroke:#333,color:#000 style C fill:#f9f,stroke:#333,color:#000 style D fill:#f9f,stroke:#333,color:#000 style P1 fill:#f0f0f0,stroke:#333,color:#000,text-align:left
In this diagram, each circle represents a vertex, and the lines between them represent edges. Notice how you can start at any vertex and trace through every edge exactly once, returning to your starting point. This is a perfect example of an Eulerian circuit because:
- Every edge is used exactly once
- The path returns to its starting point
- Each vertex has an even number of connections (degree 3 for B and D, degree 2 for A and C)
Eulerian Path Example
Let’s look at a graph that has an Eulerian path but not an Eulerian circuit:
flowchart LR subgraph "Eulerian Path Example" A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- E((E)) end subgraph "Properties" P1["• Exactly two vertices have odd degree • All vertices are connected • Must start at one odd vertex • Must end at the other odd vertex"] end style A fill:#f9f,stroke:#333,color:#000 style B fill:#9f9,stroke:#333,color:#000 style C fill:#9f9,stroke:#333,color:#000 style D fill:#9f9,stroke:#333,color:#000 style E fill:#f9f,stroke:#333,color:#000 style P1 fill:#f0f0f0,stroke:#333,color:#000,text-align:left
In this diagram, the pink vertices (A and E) have odd degrees (1 edge each), while the green vertices (B, C, D) have even degrees (2 edges each). This graph has an Eulerian path because:
- You can trace through all edges exactly once
- The path must start at vertex A (odd degree) and end at vertex E (odd degree)
- All other vertices have even degrees
Mathematical Criteria
A graph has an Eulerian circuit if and only if 2:2:
- All vertices with non-zero degree are connected
- All vertices have even degree
A graph has an Eulerian path if and only if 3:13:
- All vertices with non-zero degree are connected
- Exactly two vertices have odd degree
Implementation in C++
Here’s a C++ implementation to check if a graph has an Eulerian path or circuit:
#include <iostream>
#include <list>
using namespace std;
class Graph {
int V;
list<int> *adj;
bool isConnected() {
bool *visited = new bool[V];
for(int i = 0; i < V; i++) visited[i] = false;
// Find first non-zero degree vertex
int start = 0;
for(int i = 0; i < V; i++) {
if(adj[i].size() > 0) {
start = i;
break;
}
}
// If no edges, graph is connected
if(start == V) return true;
// Perform DFS
DFSUtil(start, visited);
// Check if all non-zero degree vertices are visited
for(int i = 0; i < V; i++) {
if(visited[i] == false && adj[i].size() > 0) return false;
}
return true;
}
void DFSUtil(int v, bool visited[]) {
visited[v] = true;
for(int i : adj[v]) {
if(!visited[i]) DFSUtil(i, visited);
}
}
int countOddDegreeVertices() {
int count = 0;
for(int i = 0; i < V; i++) {
if(adj[i].size() % 2 != 0) count++;
}
return count;
}
public:
Graph(int vertices) {
V = vertices;
adj = new list<int>[V];
}
void addEdge(int v, int w) {
adj[v].push_back(w);
adj[w].push_back(v);
}
int isEulerian() {
if(!isConnected()) return 0;
int odd = countOddDegreeVertices();
if(odd == 0) return 2; // Eulerian circuit
if(odd == 2) return 1; // Eulerian path
return 0; // Neither
}
};Implementation in Python
from collections import defaultdict
from typing import List, Tuple, Optional
class Graph:
def __init__(self):
self.graph = defaultdict(list)
self.V = 0 # Number of vertices
def add_edge(self, u: int, v: int) -> None:
"""Add an edge between vertices u and v"""
self.graph[u].append(v)
self.graph[v].append(u)
self.V = max(self.V, u + 1, v + 1)
def dfs_util(self, v: int, visited: List[bool]) -> None:
"""Utility function for DFS"""
visited[v] = True
for i in self.graph[v]:
if not visited[i]:
self.dfs_util(i, visited)
def is_connected(self) -> bool:
"""Check if the graph is connected"""
visited = [False] * self.V
# Find first non-zero degree vertex
start = 0
for i in range(self.V):
if len(self.graph[i]) > 0:
start = i
break
# If no edges, graph is connected
if start == self.V:
return True
# Perform DFS traversal
self.dfs_util(start, visited)
# Check if all non-zero degree vertices are visited
for i in range(self.V):
if not visited[i] and len(self.graph[i]) > 0:
return False
return True
def count_odd_degree_vertices(self) -> int:
"""Count vertices with odd degree"""
return sum(1 for i in range(self.V) if len(self.graph[i]) % 2 != 0)
def is_eulerian(self) -> int:
"""
Check if graph has Eulerian path or circuit
Returns:
0: Not Eulerian
1: Has Eulerian path
2: Has Eulerian circuit
"""
if not self.is_connected():
return 0
odd = self.count_odd_degree_vertices()
if odd == 0:
return 2 # Eulerian circuit
elif odd == 2:
return 1 # Eulerian path
else:
return 0 # Not Eulerian
# Example usage
def main():
# Create a graph with Eulerian circuit
g1 = Graph()
g1.add_edge(0, 1)
g1.add_edge(1, 2)
g1.add_edge(2, 3)
g1.add_edge(3, 0)
g1.add_edge(1, 3)
print("Graph 1 (should have Eulerian circuit):")
print(f"Result: {g1.is_eulerian()}")
# Create a graph with Eulerian path
g2 = Graph()
g2.add_edge(0, 1)
g2.add_edge(1, 2)
g2.add_edge(2, 3)
print("\nGraph 2 (should have Eulerian path):")
print(f"Result: {g2.is_eulerian()}")
if __name__ == "__main__":
main()Time and Space Complexity
- Time Complexity: O(V + E) 2:10
- Space Complexity: O(V + E) 2:11
This implementation can be used to check any undirected graph for Eulerian properties. The algorithm first verifies connectivity using DFS, then counts vertices with odd degrees to determine if the graph has an Eulerian circuit (all vertices even) or path (exactly two odd vertices).