Determine whether the graphs have an Euler circuit Construct

Determine whether the graphs have an Euler circuit. Construct such a circuit when one exists. If no Euler circuit exists, determine whether the graph has an Euler path and construct such a path if one exists.

A)

B)

C)

Solution

An Euler path is a path that uses every edge of a graph exactly once.

An Euler circuit is a circuit that uses every edge of a graph exactly once.

i.e. An Euler path starts and ends at different vertices and an Euler circuit starts and ends at the same vertex.

NOW,

(a) Here,we have four vertices of odd degree.

These are c, b, a, and e.

Hence, this graph would neither have have an Euler circuit nor it would have an euler path.

(b)  Here, this graph does not have an Euler circuit because we have two vertices with odd degrees which are a and d. This graph does have an Euler path (Since we know that, a connected multigraph has an Euler path but not an Euler circuit if and only if it has exactly two vertices of odd degree.).

Here, the path is as follows: a, e, c, e, b, e, d, b, a, c, d

(c) Every vertex has an even degree.

There are Euler circuits and one of them is aeaebedcecdba.