For each graph determine whether an Eulerian circuit exists

For each graph, determine whether an Eulerian circuit exists. If the graph does NOT have an Eulerian circuit, completely explain why not. If it does have an Eulerian circuit, describe them by listing all vertices in that circuit and explain your reasoning completely.

Solution

An undirected graph has Eulerian cycle if following two conditions are true.

a)All vertices have even degree.

b).All vertices with non-zero degree are connected. We don’t care about vertices with zero degree because they don’t belong to Eulerian Cycle or Path (we only consider all edges).

Graph a. c and f have odd degree.(3) graph does NOT have an Eulerian circuit

Graph b. h and g have odd degree.(3) graph does NOT have an Eulerian circuit