Euler path in the graph AB, AC, BC, CD, DE, EF, FD Step by Step

Step by step

The question

Question: find an Euler path in the graph AB, AC, BC, CD, DE, EF, DF.

edges: AB, AC, BC, CD, DE, EF, DF

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

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

It always works: the handshake rule.

2 + 2 + 3 + 3 + 2 + 2 = 14 = 2 × 7 edges

4 Find the odd vertices

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

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 C, an odd vertex.

Go to A: edge 1.

Last, F to D: edge 7.

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

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

6 Check

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

Right!

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