3.5 Paths and Cycles

Caution: In literature there is a considerable variation of terminology concerning the concepts defined in this section. When consulting a book or an article, you need to make sure which definitions are used in the particular text.

Paths and Cycles

Let $v_{0}$ and $v_{n}$ be vertices in a graph $G$ . A path in $G$ from $v_{0}$ to $v_{n}$ of length $n$ is an alternating sequence of $n + 1$ vertices and $n$ edges, $v_{0} e_{1} v_{1} e_{2} \dots v_{n - 1} e_{n} v_{n}$ , in which edge $e_{i}$ is incident on vertices $v_{i - 1}$ and $v_{i}$ for every $i = 1, \dots, n$

Note that in a simple graph, to denote a path we just need to list the sequence of vertices since two vertices are connected by only one edge, e.g. $v_{0} v_{1} \dots v_{n}$

A simple path from vertex $u$ to vertex $v$ in a graph $G$ is a path from $u$ to $v$ with no repeated vertices

Lemma 3.1

Let $G$ be a graph, and $u$ and $v$ two vertices of $G$ . There is a path from $u$ to $v$ in $G$ if and only if there is a simple path from $u$ to $v$ in $G$

Proof

Let $u$ and $v$ be vertices of a graph $G$

$(⟸)$ A simple path from $u$ to $v$ in $G$ is a path from $u$ to $v$ , so the result trivially holds

$(⟹)$ Let $P$ be a path from $u$ to $v$ . If $P$ has no repeated vertices, then $P$ is a simple path and we are done. So assume that $P$ has a repeated vertex $w$ . Let $P^{'}$ be the path obtained by going along $P$ from $u$ to the first appearance of $w$ , and then going along $P$ from the last appearance of $w$ to $v$ . So $P^{'}$ is a path from $u$ to $v$ whose length is smaller than the length of $P$ . If $P^{'}$ has no repeated vertices, then we are done. Otherwise, repeat this procedure. By repeating this procedure until there are no more repeated vertices, we end up with a simple path from $u$ to $v$

Two vertices $u$ and $v$ of a graph $G$ are said to be connected if there is a path from $u$ to $v$

A graph $G$ is connected if for every pair of vertices $u$ and $v$ of $G$ there is a path from $u$ to $v$ .

Otherwise $G$ is disconnected

A graph $H$ is a subgraph of a graph $G$ , denoted by $H \subseteq G$ , if $V (H) \subseteq V (G)$ and $E (H) \subseteq E (G)$ . A subgraph $H$ of $G$ is a proper subgraph of $G$ if $H \neq G$

A graph $H$ is an induced subgraph of a graph $G$ , if $H$ is a subgraph of $G$ such that every edge of $G$ with both endnodes in $V (H)$ is also an edge of $H$ (A subgraph but the edges aren’t changed, just less vertices). We say that $H$ is the subgraph of $G$ induced by the node set $V (H)$

Let $G$ be a graph. For $M \subseteq E (G)$ , $G ∖ M$ denotes the graph obtained from $G$ by removing the edges from $M$ . So $G ∖ M = (V (G), E (G) ∖ M) .$
For $S \subseteq V (G)$ , $G [S]$ denotes the subgraph of $G$ induced by $S$ .
For $S \subseteq V (G)$ , $G ∖ S$ denotes the graph obtained from $G$ by removing the vertices from $S$ (and therefore we also remove all edges of $E (G)$ that are incident to vertex in $S$ ). So $G ∖ S = G [V (G) ∖ S]$ (i.e. the subgraph induced by $\overset{―}{S}$ )

Let $G$ be a graph. Relation “is connected to” is an equivalence relation on $V (G)$ .
- It is Reflexive, since any vertex is trivially connected to itself by a path of length 0
- It is Symmetric, since a path from $u$ to $v$ can be traversed in the opposite direction to give a path from $v$ to $u$
- It is Transitive, since a path from $u$ to $v$ and a path from $v$ to $w$ can be combined to give a path from $u$ to $w$

So there is a partition of $V (G)$ into nonempty subsets $V_{1}, \dots, V_{k}$ such that $u$ and $v$ are connected if and only if both $u$ and $v$ belong to the same subset $V_{i}$ . For $i = 1, \dots, k$ we define $G_{i}$ to be the subgraph of $G$ induced by the node set $V_{i}$ . Induced subgraphs $G_{1}, \dots, G_{k}$ are called the components of $G$ . Note that connected graphs are those that have only one component.