Paths and Cycles as Graph Families

Two Basic Families of Graphs

Paths and cycles are among the simplest graph shapes, but recognizing them correctly requires keeping track of both vertices and edges. A larger graph may contain a path or cycle even when it has extra edges among the same vertices. Those extra edges matter if we are asking for an induced subgraph, but they do not prevent the selected edges from forming an ordinary subgraph. The distinction is important whenever a graph is specified by an edge list rather than a picture.

All graphs in this tutorial are finite and simple: they have no loops or multiple edges. A graph \(H=(W,F)\) is a subgraph of \(G=(V,E)\) if \(W\subseteq V\), \(F\subseteq E\), and every edge in \(F\) has both endpoints in \(W\). The subgraph need not include every edge of \(G\) whose endpoints are in \(W\). The induced subgraph \(G[W]\), by contrast, has vertex set \(W\) and includes every edge of \(G\) with both endpoints in \(W\).

The vertex labels in these definitions are placeholders: any graph obtained by consistently renaming the vertices has the same structure. A copy of \(P_n\) or \(C_n\) in a graph \(G\) means a subgraph isomorphic to that graph. Equivalently, we can specify distinct vertices in \(G\) in a suitable order and select the edges joining consecutive vertices, with the additional closing edge for a cycle. Other edges of \(G\) may be present but left out of the selected subgraph.

What the Edge Lists Require

For a proposed path copy, the selected vertices must be distinct and can be ordered \(x_1,\ldots,x_n\) so that the selected edge set is exactly \(x_ix_{i+1}\) for \(1\leq i<n\). There are \(n-1\) such edges. For a proposed cycle copy, the distinct vertices can be ordered \(x_1,\ldots,x_n\), with \(n\geq3\), so that the selected edges are exactly \(x_ix_{i+1}\) for \(1\leq i<n\), together with \(x_nx_1\). There are \(n\) such edges. In both cases “exactly” describes the selected subgraph, not necessarily all the edges of the larger graph between those vertices.

These descriptions give a direct test that does not depend on a drawing. First list the vertices in the proposed order. Then check each required edge against the ambient edge set. Finally, specify the subgraph’s edge set, so it is clear which edges are being used. For a cycle, also check the closing edge between the last and first listed vertices. Distinctness of the vertices prevents a repeated vertex from being mistaken for a longer path or cycle.

Proof. Suppose first that \(H\) is isomorphic to \(P_n\). By the definition of isomorphism, there is a bijection from the vertices \(v_1,\ldots,v_n\) of \(P_n\) to the vertices of \(H\) that preserves adjacency in both directions. Write \(x_i\) for the image of \(v_i\). The edges of \(P_n\) are exactly the pairs \(v_iv_{i+1}\) with \(1\leq i<n\). Because the bijection preserves adjacency in both directions, the edges of \(H\) are exactly the pairs \(x_ix_{i+1}\) in that same index range. Conversely, if such an ordering exists, the bijection \(v_i\mapsto x_i\) is a bijection of vertices and preserves adjacency in both directions, since the stated edge set contains precisely the consecutive pairs. Thus it is an isomorphism to \(P_n\).

For \(C_n\), the same reasoning applies with its defining edge set: an isomorphism sends each \(v_i\) to a distinct \(x_i\), and sends exactly the consecutive pairs and the closing pair \(v_nv_1\) to \(x_ix_{i+1}\) and \(x_nx_1\). Conversely, an ordering with exactly those edges defines a bijection preserving adjacency in both directions, and hence an isomorphism to \(C_n\). \(\square\)

Useful Checks from Degrees and Edge Counts

The edge lists also give quick checks on a proposed graph family. In \(P_n\), when \(n\geq2\), the vertices \(v_1\) and \(v_n\) each have degree \(1\), and every other vertex has degree \(2\). For \(P_1\), the sole vertex has degree \(0\). Every vertex of \(C_n\), for \(n\geq3\), has degree \(2\). These facts follow directly from the listed edges: an internal path vertex occurs in two consecutive pairs, a path endpoint occurs in one, and a cycle vertex is joined to its predecessor and successor.

Counting the edges in the definitions gives \(|E(P_n)|=n-1\) for \(n\geq1\), and \(|E(C_n)|=n\) for \(n\geq3\). For \(P_1\), the range \(1\leq i<1\) contains no indices, so the edge count is \(0=1-1\). For \(P_n\) with \(n\geq2\), there are \(n-1\) consecutive pairs. For \(C_n\), there are those \(n-1\) pairs and one closing pair, for a total of \(n\).

Proof of the checks. For \(P_n\) with \(n\geq2\), the first vertex is incident only with \(v_1v_2\), and the last only with \(v_{n-1}v_n\). Each \(v_i\) with \(1<i<n\) is incident with \(v_{i-1}v_i\) and \(v_iv_{i+1}\). This proves the stated degrees; for \(P_1\), its edge set is empty. In \(C_n\), each \(v_i\) is incident with the edge to its predecessor and the edge to its successor, where the closing edge makes these neighbors available also at the ends of the list. For \(n\geq3\), these are two distinct edges, so every degree is \(2\). The edge counts follow by counting the consecutive pairs in each defining edge set and, for the cycle, adding the one closing edge. \(\square\)

Worked Examples

Common Pitfalls and Why the Distinction Matters

A common mistake is to reject a path or cycle because the larger graph has an extra edge between its selected vertices. For example, in the first worked example, the incorrect calculation is: “The five vertices have edges \(ab,bc,cd,de,ac\), so they cannot contain \(P_5\).” This treats the induced subgraph as if it were the only allowed subgraph. The correction is to specify the selected edge set \(\{ab,bc,cd,de\}\). It is a subgraph and is isomorphic to \(P_5\); the additional edge \(ac\) only prevents the five vertices from inducing \(P_5\).

A second mistake is to use a degree pattern as a complete certificate. A path graph with \(n\geq2\) has two degree-\(1\) vertices and all its other vertices have degree \(2\), but seeing those degrees does not verify that the edges connect the vertices in one path-shaped arrangement. Likewise, degree \(2\) at every vertex is a necessary check for a cycle graph, not a replacement for checking the ordered edge set. The reliable certificate is explicit: give the distinct vertices in order and list the required edges, including the closing edge for a cycle.

Small cases should also be handled from the definitions rather than from a remembered picture. \(P_1\) has no edges, and \(P_2\) has one edge; a cycle requires at least three vertices in a simple graph. In particular, the path edge-count formula includes \(P_1\), while the cycle definition begins at \(C_3\). Keeping these conditions visible avoids applying a cycle description where its closing edge would duplicate an existing edge or fail to define a simple cycle graph.

Paths and cycles provide standard patterns for describing pieces of larger graphs. Their explicit edge lists make it possible to verify a claimed subgraph by inspection of the vertex and edge sets, while the induced-subgraph distinction clarifies exactly what has been selected. In later structural arguments, the same habit—state the vertices, state the edges, and check every required pair—helps prevent a plausible drawing from substituting for a proof.