Moving around a network

If we start at a vertex and then move along an edge (in the direction of the arrow, if it’s a directed edge) to a new vertex, we are starting a walk. We can continue the walk by selecting another edge coming out of the second vertex, then a third edge coming out of the third vertex, and so on. In a simple network we can represent a walk by a sequence of vertices. Here is a simple, undirected network, with the green arrows representing a walk around the network:

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

A walk that starts and ends at the same vertex is called closed, and if it starts and ends at different vertices it is called 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 from just looking at the sequence (and not the diagram) that’s the walk is closed, since the sequence starts and ends with the same letter.

A walk is the broadest, 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). 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, since no vertex is used more than once, except for the vertex at the start/end.