Eulerian Path and Cycle for Undirected Graph

This is extracted from GeeksforGeeks.

Eulerian Path is a path in graph that visits every edge exactly once.

Eulerian Cycle is an Eulerian Path which starts and ends on the same vertex.

A graph is called Eulerian if it has an Eulerian Cycle and called Semi-Eulerian if it has an Eulerian Path.

Properties

Eulerian Cycle

An undirected graph has Eulerian Cycle if following two conditions are true.

  1. All vertices with non-zero degree are connected. We don’t care about vertices with zero degree because the don’t belong to Eulerian Cycle or Path (we only consider all edges).

  2. All vertices have even degree.

Eulerian Path

  1. Same as condition 1 for Eulerian Cycle.

  2. If zero or two vertices have odd degree and all other vertices have even degree. Note that only one vertices with odd degree is not possible in an undirected graph (sum of all degrees is always even in an undirected graph).

Implement

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
# Python program to check if a given graph is Eulerian or not
# Complexity: O(V+E)

from collections import defaultdict

class Graph:
def __init__(self, vertices):
self.V = vertices # Number of vertices
self.graph = defaultdict(list)

def addEdge(self, u, v):
self.graph(u).append(v)
self.graph(v).append(u)

def DFSUtil(self, v, visited):
visited[u] = True
for nei in self.graph[v]:
if visited[nei] == False:
self.DFSUtil(nei, visited)

def isConnected(self):
visited = [False] * (self.V)

for i in range(self.V):
if len(self.graph[i]) > 1:
break

if i == self.V - 1:
return True

self.DFSUtil(i, visited)

for i in range(self.V):
if visited[i] == False and len(self.graph[i]) > 0:
return False

return True


def isEulerian(self):
if self.isConnected() == False:
return 'not Eulerian'
else:
odd = 0
for i in range(self.V):
if len(self.graph[i]) % 2 != 0:
odd += 1

# Note that odd count can never be 1 for undirected graph
if odd == 0:
return 'Euler Circuit (Eulerian)'
elif odd == 2:
return 'Euler Path (Semi-Eulerian)'
else:
return 'not Eulerian'
0%