# Definition:Path (Graph Theory)

*This page is about Path in the context of Graph Theory. For other uses, see Path.*

## Definition

Let $G$ be an undirected graph.

A **path** in $G$ is a **trail** in $G$ in which all **vertices** (except perhaps the first and last ones) are **distinct**.

A path between two vertices $u$ and $v$ is called a **$u$-$v$ path**.

### Subgraph

The set of vertices and edges which go to make up a **path** in a graph $G$ form a **subgraph** of $G$.

This **subgraph** itself is also referred to as a **path** in $G$.

### Open Path

An **open path** is a path in which the first and last vertices are distinct.

## Path in Digraph

In the context of a digraph the definition is similar:

Let $D = \struct {V, E}$ be a digraph.

A **path** $P$ in $D$ is:

- a sequence of
**vertices**$v_1, v_2, \ldots, v_n$ in $V$ and a sequence of**arcs**$e_1, e_2, \ldots{}, e_{n - 1}$ in $E$ such that: - $P$ begins with $v_1$ and ends with $v_n$
- in which each
**arc**$e_j$ is incident from $v_j$ and incident to $v_{j + 1}$ - all
**arcs**are**distinct** - all
**vertices**(except perhaps the first and last ones) are**distinct**.

A **path** between two vertices $u$ and $v$ is called a **path from $u$ to $v$**.

## Also known as

Some sources refer to what $\mathsf{Pr} \infty \mathsf{fWiki}$ calls a **path** as a **simple path**, and use the term **path** to define what $\mathsf{Pr} \infty \mathsf{fWiki}$ defines as a **walk**.

A **path** in a graph $G$ can be referred to as a **$G$-path**.

Some sources use the word **chain**.

Some sources refer to this as a **Hamiltonian walk** for William Rowan Hamilton.

Some sources are not careful to distinguish between a **walk** and a **path**, glossing over the possibility of repetition of vertices.

## Warning

It seems at first glance that a **path** could also be defined as a **walk** in which all vertices (except perhaps the first and last ones) are distinct.

By this definition it would appear that a **path** is automatically a **trail**, because if an edge were to be retraced in any **walk**, then the vertices at either end of it would necessarily be visited more than once.

However, under this looser definition, the **walk** $u \to v \to u$ for two adjacent vertices $u$ and $v$, for example, would fit the definition of a **path**, and therefore be a cycle.

But such a walk is not a trail, as the edge $u v$ would be traversed twice.

Hence the insistence that a **path** is a type of trail.

## Also see

- Definition:Cycle (Graph Theory): a
**closed path**: that is, a**path**in which the first and last vertices are the same.

- Results about
**paths**in the context of**Graph Theory**can be found**here**.

## Sources

- 1977: Gary Chartrand:
*Introductory Graph Theory*... (previous) ... (next): $\S 2.3$: Connected Graphs - 1979: John E. Hopcroft and Jeffrey D. Ullman:
*Introduction to Automata Theory, Languages, and Computation*... (previous) ... (next): Chapter $1$: Preliminaries: $1.2$ Graphs and Trees - 1989: Ephraim J. Borowski and Jonathan M. Borwein:
*Dictionary of Mathematics*... (previous) ... (next):**path**:**1.** - 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (previous) ... (next): $\S 2.3.4.1$: Free Trees - 1998: David Nelson:
*The Penguin Dictionary of Mathematics*(2nd ed.) ... (previous) ... (next):**path** - 1998: David Nelson:
*The Penguin Dictionary of Mathematics*(2nd ed.) ... (previous) ... (next):**walk** - 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next):**path**:**1.** - 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next):**walk** - 2014: Christopher Clapham and James Nicholson:
*The Concise Oxford Dictionary of Mathematics*(5th ed.) ... (previous) ... (next):**path**(in a graph)