[prev] 90 [next]

Euler Path and Circuit (cont)

One possible "brute-force" approach:
  • check for each path if it's an Euler path
  • would result in factorial time performance
Can develop a better algorithm by exploiting:

Theorem.   A graph has an Euler circuit if and only if
   it is connected and all vertices have even degree

Theorem.   A graph has a non-circuitous Euler path if and only if
   it is connected and exactly two vertices have odd degree