Paths, cycles

Paths

A $\text{path}$ $P_n$ is a type of $\text{graph}$ where the $\text{vertices}$ can be arranged in a sequence $v_1,v_2,\dots ,v_n$ so that the $\text{edges}$ link each consecutive pair $v_i{v}_{i+1}$.

A simple $\text{path}$ has no repeated $\text{vertices}$ or $\text{edges}$, forming a linear chain through the $\text{graph}$.

$\text{Paths}$ are fundamental for measuring distances and connectivity because the number of $\text{edges}$ in a shortest $\text{path}$ gives the distance between two $\text{vertices}$.

In applications such as routing and network flow, identifying $\text{paths}$ enables algorithms to find efficient routes through complex $\text{graphs}$.

Figure 1. Path graphs with 2, 3, 4, and 5 vertices.

$\mathbf{\text{Example}}$
A $\text{path}$ $P_4$ with $\text{vertices}$ $v_1,v_2,v_3,v_4$ has $\text{edges}$ $v_1{v}_2,v_2{v}_3,v_3{v}_4$.

$\mathbf{\text{Metaphor}}$
A $\text{path}$ is like stepping stones laid in a row across a stream, each stone connected directly to the next.

Cycles

A $\text{cycle}$ $C_n$ (or $n$-cycle) is a $\text{graph}$ whose $\text{vertices}$ $v_1,v_2,\dots ,v_n$ form a closed loop with $\text{edges}$ $v_1{v}_2,v_2{v}_3,\dots ,v_{n-1}{v}_n,v_n{v}_1$.

When $n$ is $\text{even}$, we call $C_n$ an $\text{even}$ $\text{cycle}$. When $n$ is $\text{odd}$, we call $C_n$ an $\text{odd}$ $\text{cycle}$.

$\text{Cycles}$ detect loops within a $\text{graph}$ and are key to understanding structures such as feedback circuits or non-acyclic dependencies.

In chemistry and biology, $\text{cycles}$ model ring molecules or closed metabolic pathways, revealing circular interactions.

Figure 2. Cycle graphs with $n\in \{3,4,5,6\}$ vertices.

$\mathbf{\text{Example}}$
A $\text{cycle}$ $C_3$ with $\text{vertices}$ $v_1,v_2,v_3$ has $\text{edges}$ $v_1{v}_2,v_2{v}_3,v_3{v}_1$ and forms a triangle.

$\mathbf{\text{Metaphor}}$
A $\text{cycle}$ is like a roundabout where each exit leads to the next until you return to where you started.

Connectivity via Paths and Cycles

A $\text{graph}$ $G$ is said to have a $\text{cycle}$ if there exists a subgraph of $G$ isomorphic to some $\text{cycle}$ $C_k$.

Two $\text{vertices}$ $u$ and $v$ in $G$ are $\text{connected}$ if there is a subgraph of $G$ $\text{isomorphic}$ to a $\text{path}$ $P_k$ with first $\text{vertex}$ $u$ and last $\text{vertex}$ $v$.

Connectivity via $\text{paths}$ defines whether information or flow can traverse the $\text{graph}$ from one point to another.

The presence or absence of $\text{cycles}$ differentiates acyclic structures like trees from more complex networks with loops.

$\mathbf{\text{Example}}$
In a tree $\text{graph}$, any two $\text{vertices}$ are connected by exactly one $\text{path}$ and there are no $\text{cycles}$.

$\mathbf{\text{Metaphor}}$
Connectivity in a $\text{graph}$ is like a road network where towns are $\text{vertices}$ and roads are $\text{edges}$; $\text{paths}$ are routes, and $\text{cycles}$ are loops you can drive around.

Conclusion

We have defined two fundamental structures in graph theory: the linear $\text{path}$ $P_n$ and the closed $\text{cycle}$ $C_n$, each characterized by specific sequences of $\text{vertices}$ and $\text{edges}$.

Paths serve as the building blocks for measuring distance and ensuring connectivity between $\text{vertices}$, while cycles reveal loops that distinguish acyclic trees from more intricate networks.

Understanding how $\text{paths}$ and $\text{cycles}$ embed into a $\text{graph}$ via subgraph isomorphism underpins key concepts of connectivity and network structure analysis.