12.3: Paths and Cycles

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

Recall the definition of a walk. As we saw in Example 12.2.1, the vertices and edges in a walk do not need to be distinct.

There are many circumstances under which we might not want to allow edges or vertices to be re-visited. Efficiency is one possible reason for this. We have a special name for a walk that does not allow vertices to be re-visited.

Definition: Path

A walk in which no vertex appears more than once is called a path.

Notation

For $$n ≥ 0$$, a graph on $$n + 1$$ vertices whose only edges are those used in a path of length $$n$$ (which is a walk of length $$n$$ that is also a path) is denoted by $$P_n$$. (Notice that $$P_0 \cong K_1$$ and $$P_1 \cong K_2$$.)

Notice that if an edge were to appear more than once in a walk, then both of its endvertices would also have to appear more than once, so a path does not allow vertices or edges to be re-visited.

Example $$\PageIndex{1}$$

In the graph

$$(a, f, c, h)$$ is a path of length $$3$$. However, $$(a, f, c, h, d, f)$$ is not a path, even though no edges are repeated, since the vertex $$f$$ appears twice. Both are walks.

Proposition $$\PageIndex{1}$$

Suppose that $$u$$ and $$v$$ are in the same connected component of a graph. Then any $$u − v$$ walk of minimum length is a path. In particular, if there is a $$u − v$$ walk, then there is a $$u − v$$ path.

Proof

Since $$u$$ and $$v$$ are in the same connected component of a graph, there is a $$u − v$$ walk.

Towards a contradiction, suppose that we have a $$u − v$$ walk of minimum length that is not a path. By the definition of a path, this means that some vertex $$x$$ appears more than once in the walk, so the walk looks like:

$(u = u_1, . . . , u_i = x, . . . , u_j = x, . . . , u_k = v),$

and $$j > i$$. Observe that the following is also a $$u − v$$ walk:

$(u = u_1, . . . , u_i = x, u_{j+1}, u_{j+2}, . . . , u_k = v).$

Since consecutive vertices were adjacent in the first sequence, they are also adjacent in the second sequence, so the second sequence is a walk. The length of the first walk is $$k − 1$$, and the length of the second walk is $$k − 1 − (j − i)$$. Since $$j > i$$, the second walk is strictly shorter than the first walk. In particular, the first walk was not a $$u − v$$ walk of minimum length. This contradiction serves to prove that every $$u − v$$ walk of minimum length is a path.

This allows us to prove another interesting fact that will be useful later.

Proposition $$\PageIndex{2}$$

Deleting an edge from a connected graph can never result in a graph that has more than two connected components.

Proof

Let $$G$$ be a connected graph, and let $$u_v$$ be an arbitrary edge of $$G$$. If $$G \setminus \{u_v\}$$ is connected, then it has only one connected component, so it satisfies our desired conclusion. Thus, we assume in the remainder of the proof that $$G \setminus \{u_v\}$$ is not connected.

Let $$G_u$$ denote the connected component of $$G \setminus \{u_v\}$$ that contains the vertex $$u$$, and let $$G_v$$ denote the connected component of $$G \setminus \{u_v\}$$ that contains the vertex $$v$$. We aim to show that $$G_u$$ and $$G_v$$ are the only connected components of $$G \setminus \{u_v\}$$.

Let $$x$$ be an arbitrary vertex of $$G$$, and suppose that $$x$$ is a vertex that is not in $$G_u$$. Since $$G$$ is connected, there is a $$u − x$$ walk in $$G$$, and therefore by Proposition 12.3.1 there is a $$u − x$$ path in $$G$$. Since $$x$$ is not in $$G_u$$, this $$u−x$$ path must use the edge $$u−v$$, so must start with this edge since $$u$$ only occurs at the start of the path. Therefore, by removing the vertex $$u$$ from the start of this path, we obtain a $$v − x$$ path that does not use the vertex $$u$$. This path cannot use the edge $$u_v$$, so must still be a path in $$G \setminus \{u_v\}$$. Therefore $$x$$ is a vertex in $$G_v$$.

Since $$x$$ was arbitrary, this shows that every vertex of $$G$$ must be in one or the other of the connected components $$G_u$$ and $$G_v$$, so there are at most two connected components of $$G \setminus \{u_v\}$$. Since $$u_v$$ was an arbitrary edge of $$G$$ and $$G$$ was an arbitrary connected graph, this shows that deleting any edge of a connected graph can never result in a graph with more than two connected components.

A cycle is like a path, except that it starts and ends at the same vertex. The structures that we will call cycles in this course, are sometimes referred to as circuits.

Definition: Cycle

A walk of length at least $$1$$ in which no vertex appears more than once, except that the first vertex is the same as the last, is called a cycle.

Notation

For $$n ≥ 3$$, a graph on $$n$$ vertices whose only edges are those used in a cycle of length $$n$$ (which is a walk of length $$n$$ that is also a cycle) is denoted by $$C_n$$.

The requirement that the walk have length at least $$1$$ only serves to make it clear that a walk of just one vertex is not considered a cycle. In fact, a cycle in a simple graph must have length at least $$3$$.

Example $$\PageIndex{2}$$

In the graph from Example 12.3.1, $$(a, e, f, a)$$ is a cycle of length $$3$$, and $$(b, g, d, h, c, f, b)$$ is a cycle of length $$6$$.

Here are drawings of some small paths and cycles:

We end this section with a proposition whose proof will be left as an exercise.

Proposition $$\PageIndex{3}$$

Suppose that $$G$$ is a connected graph. If $$G$$ has a cycle in which $$u$$ and $$v$$ appear as consecutive vertices (so $$u_v$$ is an edge of $$G$$) then $$G \setminus \{u_v\}$$ is connected.

Exercise $$\PageIndex{1}$$

1) In the graph

(a) Find a path of length $$3$$.

(b) Find a cycle of length $$3$$.

(c) Find a walk of length $$3$$ that is neither a path nor a cycle. Explain why your answer is correct.

2) Prove that in a graph, any walk that starts and ends with the same vertex and has the smallest possible non-zero length, must be a cycle.

3) Prove Proposition 12.3.3.

4) Prove by induction that if every vertex of a connected graph on $$n ≥ 2$$ vertices has valency $$1$$ or $$2$$, then the graph is isomorphic to $$P_n$$ or $$C_n$$.

5) Let $$G$$ be a (simple) graph on $$n$$ vertices. Suppose that $$G$$ has the following property: whenever $$u \nsim v$$, $$dG(u) + dG(v) ≥ n − 1$$. Prove that $$G$$ is connected.

This page titled 12.3: Paths and Cycles is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Joy Morris.