Paths and Simple Routes

What Makes a Route a Path?

A route through a graph is recorded as a sequence of vertices, with each consecutive pair joined by an edge. The order matters: the sequence records where the route starts, where it goes next, and where it ends. A path is a particularly simple kind of route: it never visits a vertex twice. This condition makes it useful to describe a route between two vertices without loops back through places already visited.

All graphs in this tutorial are finite, undirected and simple: they have no loops or multiple edges. A walk is a sequence \(v_0,v_1,\ldots,v_\ell\) such that \(v_{i-1}v_i\in E(G)\) for each \(i=1,\ldots,\ell\). Its length is \(\ell\), the number of consecutive pairs. A walk is allowed to repeat vertices or edges. A trail, as defined in the earlier material on trails, does not repeat edges; it may still repeat vertices.

The order of a path’s vertices specifies its direction of travel, but the graph itself is undirected. Reversing the sequence therefore gives another path using the same edges in reverse order. A path of length \(0\) consists of one vertex \(v_0\): its two endpoint positions both refer to \(v_0\), and it has no internal vertices. A path of length \(1\) has two distinct endpoints and no internal vertices.

The requirement that vertices be distinct applies to the whole sequence, including both endpoints. Thus, for a positive-length path, the endpoints must differ. A sequence with an edge between every consecutive pair is a walk, but that alone does not make it a path: one must also check that no vertex appears twice.

Testing a Candidate Sequence

To check whether a proposed sequence is a path in a given graph, two separate conditions must hold. First, every consecutive pair must be an edge of the graph. Second, no vertex may occur more than once. If the first condition fails, the sequence is not even a walk in that graph. If the first condition holds but the second fails, it is a walk but not a path.

This test is direct: look up each required consecutive edge, then check the list of vertices for repetitions. The order of these checks helps explain different failures. A missing edge invalidates the proposed route before repeated vertices matter; a repeated vertex invalidates path status even when every required edge exists.

Endpoints and Internal Vertices

For a path written as \(v_0,v_1,\ldots,v_\ell\), the endpoints are determined by the first and last positions, not by how many edges meet those vertices elsewhere in the graph. The internal vertices are precisely the entries between those positions. If the path has length \(\ell\geq 1\), it has \(\ell+1\) listed vertices and \(\ell-1\) internal vertices: removing the first and last entries from the list leaves \(\ell-1\) entries. For \(\ell=0\), there is one listed vertex and no internal vertices.

Basic Properties of Paths

Proof. Let \(v_0,v_1,\ldots,v_\ell\) be a path. For each \(i=1,\ldots,\ell\), the pair \(v_{i-1}v_i\) is an edge. Since the graph is undirected, \(v_iv_{i-1}\) is the same edge. Therefore the reversed sequence \(v_\ell,v_{\ell-1},\ldots,v_0\) has an edge between every consecutive pair. It contains exactly the same vertices as the original sequence, so they remain distinct. Thus the reversed sequence is a path. It has \(\ell\) consecutive pairs, so its length is \(\ell\), and its endpoints are \(v_\ell\) and \(v_0\). When \(\ell=0\), reversal leaves the one-vertex sequence unchanged, so the conclusion also holds.

Now choose indices \(i,j\) with \(0\leq i\leq j\leq\ell\). The consecutive segment \(v_i,v_{i+1},\ldots,v_j\) has an edge between each consecutive pair because those pairs were also consecutive in the original path. Its vertices are distinct because they are selected from a list of distinct vertices. It is therefore a path, including when \(i=j\), in which case it is a one-vertex path of length \(0\). \(\square\)

A consequence of the proposition is that any consecutive portion of a path can be used on its own. For example, from the path \(1,2,6,5,4\), the segment \(2,6,5\) is a path: \(26,65\in E\), and \(2,6,5\) are distinct. Its endpoints are \(2\) and \(5\), its internal vertex is \(6\), and its length is \(2\).

Joining paths requires more care. Suppose one path ends where another begins, so their sequences can be placed one after the other without repeating that shared endpoint at the join. The combined sequence certainly has the consecutive edges needed for a walk. But it is a path only if the combined list has no repeated vertices. The two paths may share a vertex other than their joining endpoint.

A Common Mistake

A frequent error is to check that every consecutive pair is an edge and then call the sequence a path. That checks only that the sequence is a walk; the distinct-vertices test is still required. For instance, in the graph of the first worked example, the sequence \(a,c,b,a\) uses the edges \(ac,cb,ba\). A mistaken calculation might say: “There are three edges, so it is a path of length \(3\).” The length calculation is correct, but the conclusion is not: \(a\) occurs twice. The correction is to report a walk of length \(3\) (in this case, also a trail), not a path.

Another counting error is to report \(\ell\) internal vertices for a path of length \(\ell\). For positive length, there are \(\ell+1\) vertex positions, of which the first and last are endpoints, leaving \((\ell+1)-2=\ell-1\) internal vertices. In the path \(1,2,6,5,4\), the length is \(4\), but the internal vertices are the three entries \(2,6,5\), not four. For length \(0\), the path consists of one vertex and has no internal vertices.

Careful sequence checks are useful whenever a problem asks whether a particular route is a path or asks for the parts of a specified path. Keep the two tests separate: verify the edges first, then verify that the vertices do not repeat. Once the sequence passes both tests, its endpoints and internal vertices are read directly from their positions.