12.3: Paths and Cycles

Last updated
Save as PDF

Page ID: 60135

Joy Morris
University of Lethbridge

$ \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}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$\newcommand{\avec}{\mathbf a}$ $\newcommand{\bvec}{\mathbf b}$ $\newcommand{\cvec}{\mathbf c}$ $\newcommand{\dvec}{\mathbf d}$ $\newcommand{\dtil}{\widetilde{\mathbf d}}$ $\newcommand{\evec}{\mathbf e}$ $\newcommand{\fvec}{\mathbf f}$ $\newcommand{\nvec}{\mathbf n}$ $\newcommand{\pvec}{\mathbf p}$ $\newcommand{\qvec}{\mathbf q}$ $\newcommand{\svec}{\mathbf s}$ $\newcommand{\tvec}{\mathbf t}$ $\newcommand{\uvec}{\mathbf u}$ $\newcommand{\vvec}{\mathbf v}$ $\newcommand{\wvec}{\mathbf w}$ $\newcommand{\xvec}{\mathbf x}$ $\newcommand{\yvec}{\mathbf y}$ $\newcommand{\zvec}{\mathbf z}$ $\newcommand{\rvec}{\mathbf r}$ $\newcommand{\mvec}{\mathbf m}$ $\newcommand{\zerovec}{\mathbf 0}$ $\newcommand{\onevec}{\mathbf 1}$ $\newcommand{\real}{\mathbb R}$ $\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$ $\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$ $\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$ $\newcommand{\laspan}[1]{\text{Span}\{#1\}}$ $\newcommand{\bcal}{\cal B}$ $\newcommand{\ccal}{\cal C}$ $\newcommand{\scal}{\cal S}$ $\newcommand{\wcal}{\cal W}$ $\newcommand{\ecal}{\cal E}$ $\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$ $\newcommand{\gray}[1]{\color{gray}{#1}}$ $\newcommand{\lgray}[1]{\color{lightgray}{#1}}$ $\newcommand{\rank}{\operatorname{rank}}$ $\newcommand{\row}{\text{Row}}$ $\newcommand{\col}{\text{Col}}$ $\renewcommand{\row}{\text{Row}}$ $\newcommand{\nul}{\text{Nul}}$ $\newcommand{\var}{\text{Var}}$ $\newcommand{\corr}{\text{corr}}$ $\newcommand{\len}[1]{\left|#1\right|}$ $\newcommand{\bbar}{\overline{\bvec}}$ $\newcommand{\bhat}{\widehat{\bvec}}$ $\newcommand{\bperp}{\bvec^\perp}$ $\newcommand{\xhat}{\widehat{\xvec}}$ $\newcommand{\vhat}{\widehat{\vvec}}$ $\newcommand{\uhat}{\widehat{\uvec}}$ $\newcommand{\what}{\widehat{\wvec}}$ $\newcommand{\Sighat}{\widehat{\Sigma}}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\newcommand{\amp}{&}$ $\definecolor{fillinmathshade}{gray}{0.9}$

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

$clipboard_edb7270687d0dc73c8115c27e894fd21b.png$

$(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:

$clipboard_ea501d80f22da06bc918ea61e6a90363c.png$

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

$clipboard_ed28261d07020096cc0ed35c4b9e4e9f9.png$

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

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

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.

Search

Text Color

Text Size

Margin Size

Font Type