[prev] 89 [next]

Euler Path and Circuit

Euler path problem:
  • find a path connecting two vertices v,w in graph G
  • such that the path includes each edge exactly once
    (note: the path does not have to be simple ⇒ can visit vertices more than once)
If v = w, the we have an Euler circuit

[Diagram:Pic/euler-path-tour.png]

Many real-world applications require you to visit all edges of a graph:

  • Postman
  • Garbage pickup
  • …
Problem named after Swiss mathematician, physicist, astronomer, logician and engineer Leonhard Euler (1707 — 1783)