8.06 Euler networks and trails

Amazingly, it is possible to determine if an undirected network will have an Euler trail or circuit without having to actually find it. Here’s how to tell:

• If a walk that includes every edge has exactly two vertices of odd degree, then it is an Eulerian trail.

• If a walk that includes every edge has only vertices of even degree, then it is an Eulerian circuit.

Still, it can take some practice to get proficient at being able to find Euler paths or Euler circuits-knowing they exist is not the same as seeing one in front of you. To help us we are going to us a procedure called Fleury's Algorithm (pronounced flur-ee). It was first published by a French mathematician named Fleury in 1883 (his given name seems to be lost to history).

1. Make sure the graph has either 0 or 2 vertices with odd degree.

2. If there are no edges with odd degree, start anywhere. If there are 2, pick one of them to start from.

3. Follow edges one at a time, eliminating the edges you pick from the network as you go.

   • If you have a choice between a bridge and a non-bridge from the remaining edges, always choose the non-bridge.

4. Stop when you run out of edges.

Seems simple enough-let’s try it out:

This algorithm will find the Euler trail (or circuit) every time. It helps best in the tricky situations where you don’t know which edge to pick-if you choose a bridge before a non-bridge you won’t be able to get back.

For directed networks, we can still have Euler trails and Euler circuits, but there’s no easy way to find them like there is for undirected networks, you just have to give it a go. Imagine the below directed network represents a garbage collection model:

Can you find the Euler circuit now you know Fleury's algorithm? Since you’re looking for a circuit, it doesn’t matter which vertex you start from. Use the Hamiltonian cycle we found earlier to help you.

One final note before we finish this section: a network can be a traversable/Euler network, a traceable/Hamiltonian network, both, or neither, as these examples demonstrate:

The first is an Euler and a Hamiltonian network, the second is only a Hamiltonian network, the third is only an Euler network, and the fourth is neither.

Traceable vs traversable:

1. A network is traceable if there is a path that visits every vertex, and Hamiltonian if you can do it with a cycle (closed path).

2. A network is traversable if there is a trail that uses every edge, and Eulerian if you can do it with a circuit (closed trail).

Examples

Example 1

Consider the network below:

a

Does the network have an Euler trail? Does it have an Euler circuit?

A

The graph has an Euler circuit (and therefore an Euler trail).

B

The graph has an Euler trail but not an Euler circuit.

C

The graph does not have an Euler trail.

Worked Solution

Create a strategy

Find the degree of every vertex.

Apply the idea

Vertex	Degree
A	2
B	3
C	3
D	4
E	2
F	2

The table shows the degree of each vertex.

Based on the table, not every vertex of the network has an even degree and it can also be noticed that exactly two vertices have an odd degree. This means that the network has an Euler trail but not an Euler circuit.

So the correct answer is option B.

Watch question walkthrough

b

Using Fleury's algorithm, which vertex or vertices can the trail start at? Select all correct options:

A

A

B

B

C

C

D

D

E

E

F

F

Worked Solution

Create a strategy

Choose one of the two vertices of odd degree.

Apply the idea

In part (a), the vertices of odd degree are B and C.

So the trail can start at either B or C.

Watch question walkthrough

c

Beth has started to trace an Euler trail through the graph, by moving along the vertices B, \, C, \, D. According to Fleury's algorithm, which vertices are possible to travel to next along such a trail? Select all the correct options.

A

A

B

B

C

C

D

D

E

E

F

F

Worked Solution

Create a strategy

Draw the current trail on the graph.

Apply the idea

The diagram shows Beth's current trail, with edges already traversed as dotted lines.

From D there are edges to B, C, E, and F.

Beth cannot return to C as that edge has already been used.

If she travels to B then she will complete a circuit and not be able to reach edges DE or EF unless she repeats an edge.

So the vertices that are possible to travel to next are E and F.

Watch question walkthrough

d

Write a Euler trail for the network that completes Beth's journey.

Worked Solution

Create a strategy

Write a circuit that passes over all edges only once, starting and ending at different vertices.

Apply the idea

From part (c) we know that the trail starts with B,\,C,\,D, then can go to either E or F.

We can choose to go to E, as shown in the diagram.

Now we move to traverse the remaining solid edges to get the Euler trail: E,F,D,B,A,C

Watch question walkthrough