Identifying Euler circuits and Euler paths

Identifying Euler circuits and Euler paths:

Identifying Euler circuits and Euler paths:

Undirected graphs:

• The graph G 1 has an Euler circuit, for example a,e,c,d,e,b,a .
• The graph G2 has neither an Euler circuit nor an Euler path.
• The graph G3 doesn’t have an Euler circuit but it has an Euler path, namely, a,d,c,e,b,c,a,b .

Directed graphs:

Directed graphs:

• The graph H1 has an Euler path, namely d,a,b,d,c,b .
• The graph H2 has an Euler circuit, namely, a,g,c,b,g,e,d,f,a.

Theorem 1: A connected multigraph with at least two vertices has an Euler circuit if and only if each of its vertices has even degree.