8.04 Walks and paths

A walk describes the process of starting at a vertex and moving along an edge (in the direction of the arrow) to a new vertex. Continue the walk by following another edge to a second vertex,  a third edge to a  third vertex, and so on. In a simple network a walk is represented by a sequence of vertices. Here is a simple, undirected network, with the green arrows representing a walk around the network:

We can describe this walk as the sequence $ABAEFDE$ABAEFDE.

A walk that starts and ends at the same vertex is closed, and if it starts and ends at different vertices it is open. The walk above is open - below is a different walk on the same network:

This walk has sequence $ABADFCGDEA$ABADFCGDEA. Since it starts and ends at the same vertex, it is closed. We can also tell by looking at the sequence (and not the diagram) that’s the walk is closed, since the sequence starts and ends with the same letter.

Paths and cycles

A walk is the most general definition of how we can move around a network. Sometimes we want to impose a stricter condition - if we say that the walk cannot use the same vertex more than once, we call it a path (we can reuse the start/end vertex only). If the path is closed, we call it a cycle. Here are two different paths, one open and one closed, on the same network:

The green walk $DGCFEA$DGCFEA on the left is an open path, since no vertex is used more than once, and it starts and ends at different vertices. The orange walk $BCFDEAB$BCFDEAB on the right is a closed path(cycle), since no vertex is used more than once, except for the vertex at the start/end.

Trails and circuits

If a walk cannot use the same edge more than once, it is a trail if it’s open and a circuit if it’s closed. Here is one of each on the same network:

The blue walk $ADFEDGCF$ADFEDGCF on the left is a trail, since no edge is used more than once, and it is open. The red walk $GCFEDFADG$GCFEDFADG on the right is a circuit, since no edge is used more than once, and it is closed.

Note:

• All paths are trails
• All cycles are circuits.

Summary

Every sequence of edges is a walk. A walk can be open (start/end vertices different) or closed (start/end vertices same).

If edges can’t repeat, the walk is a trail.  A closed trail is a circuit.

If vertices can’t repeat, the walk is a path. A closed path is a cycle.

Practice questions

Question 1

Question 2

Traversable networks

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

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

Practice questions

Question 3

Question 4

Question 5