Does the graph AB, BC, CA, CD, DE, EC have an Euler circuit Step by Step

Step by step

The question

Question: does the graph AB, BC, AC, CD, DE, CE have an Euler circuit?

edges: AB, BC, AC, CD, DE, CE

1 Draw the graph

Each letter is a vertex: a dot.

Each pair is an edge: a line between two vertices.

An Euler path uses every edge exactly once.

An Euler circuit also ends where it started.

Euler path: every edge once

Euler circuit: and back to the start

2 Count the degrees

The degree of a vertex is how many edges touch it.

A has 2.

B has 2.

And so on.

3 Add the degrees

Add the degrees: 12.

That is 2 times the 6 edges, because each edge has two ends.

It always works: the handshake rule.

2 + 2 + 4 + 2 + 2 = 12 = 2 × 6 edges

4 Find the odd vertices

The rule: each time we pass through a vertex we use two of its edges, one in and one out.

So only the start and the end can be odd.

0 odd: circuit (start anywhere)

2 odd: path from one odd to the other

more: no Euler path

Careful!

With no odd vertices we can start anywhere, and we come back to the start.

Careful: a circuit ends where it started

5 Walk the route

Start at A.

Go to B: edge 1.

Last, C to A: edge 6.

The circuit: A, B, C, D, E, C, A.

= circuit: A, B, C, D, E, C, A

6 Check

Check: every edge has exactly one number, 1 to 6, and there are 6 edges.

Right!

numbers 1 to 6, 6 edges: each used once

Let's look back.

First: draw the graph.

Then: count the degrees.

Then: add the degrees.

Then: find the odd vertices.

Then: walk the route.

Last: check.

Answer