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

Step by step

The question

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

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

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

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.

3 + 3 + 3 + 3 = 12 = 2 × 6 edges

4 Find the odd vertices

Ring the vertices with an odd degree: A, B, 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!

However we try, we would get stuck at an odd vertex.

Careful: more than 2 odd vertices: no Euler path

4 odd vertices: there is no Euler path, and no circuit.

= no Euler path: 4 odd vertices

Let's look back.

First: draw the graph.

Then: count the degrees.

Then: add the degrees.

Last: find the odd vertices.

Answer