Determine if a graph has an Eulerian circuit, trail, or neither and explain why.

Question

Let G be the graph having V (G) = {a, b, c, d, e, f} and E(G) =

ad, ae, bc, be, cd, de, df, ef. Does G have an Eulerian circuit, trail, or neither?

Explain why.

Answer 1

Start by finding the degree (number of edges) of each vertex. Here 'd' and 'e' both have degree 4, and all other vertices have degree 2. Also check that the graph is connected, which can be done here by drawing a picture. In general you could apply Warshall's Algorithm.

A connected graph has an Eulerian circuit/cycle if and only if all vertices have even degree, which is the case for this graph.

A connected graph has an Eulerian trail/path that is not a circuit/cycle if and only if there are exactly two vertices with odd degree (the path will start at one such vertex and end at the other). This is not the case for this graph.