Graph Theory37 sections · 1633 units
Open in Course

Conditions for Undirected Graphs

When Euler paths exist in undirected graphs.

For an undirected connected graph:

Euler circuit exists if and only if every vertex has even degree.

Euler path exists if and only if exactly 00 or 22 vertices have odd degree.

  • If 00 odd vertices: Euler circuit exists (start anywhere)
  • If 22 odd vertices: Euler path exists (start at one odd vertex, end at the other)
  • If more than 22 odd vertices: no Euler path exists

Why? Each time you enter a vertex, you must leave it. If degree is odd, you'll get stuck. The exceptions are start and end vertices of a path.