An

**Euler circuit**of a graph G is a simple circuit that contains every edge of G.
A connected
multigraph has an Euler circuit if and only if each of its vertices has even
degree.

There are
several Euler circuits in the above graph. (a,b,e,c,d,e,a) and (d,c,e,b,a,e,d)
are examples. Any path that doesn’t start at ‘e’ could be an Euler circuit.

An

**Euler path**of graph G is a simple path containing every edge of G.
A connected
multigraph has an Euler path but not an Euler circuit if and only if it has
exactly two vertices of odd degree.

The above graph
has two vertices (a and b) of odd degree; thus, it contains an Euler path (but
not an Euler circuit). (b,e,d,c,a,b,d,a) and (a,c,d,e,b,d,a,b) are examples.

## 0 Comments