Week 06b: Graph Algorithms 1 (51)

Euler Path and Circuit (cont)

Assume the existence of degree(g,v) (degree of a vertex, cf. problem set week 6)

Algorithm to check whether a graph has an Euler path:

hasEulerPath(G,src,dest):
|  Input  graph G, vertices src,dest
|  Output true if G has Euler path from src to dest
|         false otherwise
|
|  if src≠dest then
|     if degree(G,src) is even ∨ degree(G,dest) is even then
|        return false
|     end if
|  else if degree(G,src) is odd then
|     return false
|  end if
|  for all vertices v∈G do
|     if v≠src ∧ v≠dest ∧ degree(G,v) is odd then
|        return false
|     end if
|  end for
|  return true