Graph Path

Last updated Nov 1, 2022

Let $G = (V, E)$ be a Directed Graph. A Graph Path of length $n \in \mathbb{N}$ from vertex $u \in V$ to $v \in V$ is a Tuple $(e_{1}, e_{2}, \dots, e_{n}) \in E^{n}$ so that

1. $e_{1} = (u, x)$ for some $x \in V$
2. $e_{2} = (y, v)$ for some $y \in V$
3. $e_{i} = (x, y)$ and $e_{i+1} = (y, z)$ for some $x,y,z \in V$ for all $i \in [n]$

1. The Empty Tuple $()$ is a Graph Path from $v \in V$ to itself for all $v \in V$. It has length $0$.
2. Suppose $P$ is a Graph Path of length $n \in \mathbb{N}$ from $u \in V$ to $v \in V$. We let $V(P)$ signify the Tuple $(e_{1,1} = u, e_{2,1}, \dots, e_{n,1}, v) \subset V^{n+1}$.

Let $G$ be an Undirected Graph. Then a Graph Path of length $n \in \mathbb{N}$ from from vertex $u \in V$ to $v \in V$ is a Graph Path of length $n \in \mathbb{N}$ on the Directed Graph representation of $G$.

• Natural Numbers
• Graph Edge