8.05 Traverse connected graphs

If a network has a trail or circuit that uses every edge, it is described as traversable (sometimes semi-Eulerian). This special walk is then called an Euler trail - If it’s open or an Euler circuit if it’s closed, named after the same Euler that gave us Euler’s formula. If a network has an Euler circuit we call it an Euler network (sometimes Eulerian).

Some texts refer to such a trail as an Euler path, but this special walk is a trail (since vertices can be repeated), not a path.

You can think about a traversable networks as ones where you can start at a vertex and draw in all the edges without taking your pen (or finger or stylus) off the page (or screen). Here are two traversable networks, the one on the right is an Euler network:

Each network has a trail that uses every edge exactly once. The trail on the right is closed, so it is a circuit, and any vertex can be the start/end.

Examples

Example 1

Consider the networks below:

A

B

C

D

a

Which one of the networks is traversable?

Worked Solution

Create a strategy

Choose a network where you can draw the network by passing through each edge exactly once without taking your pen/finger/stylus off the page.

Apply the idea

Among the choices, only Option C is traversable since we can move through all its vertices and edges without crossing an edge more than once on this network.

Watch question walkthrough

b

The traversable network from part (a) has been labelled below:

Which vertices can you start at in order to traverse the network? Select the most correct answer only.

A

A,C and G

B

D \text{ and } F

C

Just C

D

B and E

E

Any of the vertices

F

Just D

Worked Solution

Create a strategy

Find a way of traversing the network by choosing which vertex to start and which vertex to finish at.

Apply the idea

Notice that we can traverse this network by doing a loop and ending up where we started. This means that we can start at any of the vertices in order to traverse this network, and ending on the same vertex where you begin to trace the path.

So, the correct answer is Option E.

Watch question walkthrough