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

Step by step

The question

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

edges: AB, AC, BC, BD, CD

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: 10.

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

It always works: the handshake rule.

2 + 3 + 3 + 2 = 10 = 2 × 5 edges

4 Find the odd vertices

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

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 C: edge 5.

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

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

6 Check

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

Right!

numbers 1 to 5, 5 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