Week 3: Graph Data Structures and Algorithms (93)

Euler Path and Circuit (cont)

Assume the existence of degree(g,v) (degree of a vertex, cf. problem set 1 exercise 2 this week)

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       // non-circuitous path
|     if degree(G,src) or degree(G,dest) is even then
|        return false
|     end if
|  else if degree(G,src) is odd then  // circuit
|     return false
|  end if
|  for all vertices v∈G do
|     if v≠src and v≠dest and degree(G,v) is odd then
|        return false
|     end if
|  end for
|  return true