# Definition:Path (Graph Theory)

*This page is about a path in Graph Theory. For other uses, see Definition:Path.*

## Definition

A **path** is a trail 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**.

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

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

### Open Path

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

## Also known as

Some sources call this a **simple path**, and use the term **path** to define what we have here as a walk.

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

## Also see

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

## 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.

## Sources

- 1977: Gary Chartrand:
*Introductory Graph Theory*... (previous) ... (next): $\S 2.3$: Connected Graphs - 1998: David Nelson:
*The Penguin Dictionary of Mathematics*(2nd ed.) ... (previous) ... (next): Entry:**walk** - 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next): Entry:**walk** - 2014: Christopher Clapham and James Nicholson:
*The Concise Oxford Dictionary of Mathematics*(5th ed.) ... (previous) ... (next): Entry:**path**(in a graph)