Euler path in the graph AB, AD, BC, BD, CD, DE Step by Step

Step by step

The question

Question: find an Euler path in the graph AB, AD, BC, BD, CD, DE.

edges: AB, AD, BC, BD, CD, DE

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 3.

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 + 3 + 2 + 4 + 1 = 12 = 2 × 6 edges

4 Find the odd vertices

Ring the vertices with an odd degree: B and E.

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!

If we start at an even vertex, we get stuck before the end.

Start at one odd vertex, end at the other.

Careful: not start at A ✗

5 Walk the route

Start at B, an odd vertex.

Go to A: edge 1.

Last, D to E: edge 6.

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

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

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