# path

\xyoptionall

A *path* in a graph is a finite sequence^{} of alternating vertices and edges, beginning and ending with a vertex, ${v}_{1}{e}_{1}{v}_{2}{e}_{2}{v}_{3}\mathrm{\dots}{e}_{n-1}{v}_{n}$ such that every consecutive pair of vertices ${v}_{x}$ and ${v}_{x+1}$ are adjacent and ${e}_{x}$ is incident^{} with ${v}_{x}$ and with ${v}_{x+1}$. Typically, the edges may be omitted when writing a path (e.g., ${v}_{1}{v}_{2}{v}_{3}\mathrm{\dots}{v}_{n}$) since only one edge of a graph may connect two adjacent vertices. In a multigraph^{}, however, the choice of edge may be significant.

The length of a path is the number of edges in it.

Consider the following graph:

$$\text{xymatrix}A\text{ar}\mathrm{@}-[r]\mathrm{\&}B\text{ar}\mathrm{@}-[d]D\text{ar}\mathrm{@}-[u]\mathrm{\&}C\text{ar}\mathrm{@}-[l]$$ |

Paths include (but are certainly not limited to) $ABCD$ (length 3), $ABCDA$ (length 4), and $ABABABABADCBA$ (length 12). $ABD$ is not a path since $B$ is not adjacent to $D$.

In a digraph^{}, each consecutive pair of vertices must be connected^{} by an edge with the proper orientation^{}; if $e=(u,v)$ is an edge, but $(v,u)$ is not, then $uev$ is a valid path but $veu$ is not.

Consider this digraph:

$$\text{xymatrix}G\text{ar}[r]\text{ar}[d]\mathrm{\&}H\text{ar}[d]\text{ar}[l]J\mathrm{\&}I\text{ar}[l]$$ |

$GHIJ$, $GJ$, and $GHGHGH$ are all valid paths. $GHJ$ is not a valid path because $H$ and $J$ are not connected. $GJI$ is not a valid path because the edge connecting $I$ to $J$ has the opposite orientation.

Title | path |
---|---|

Canonical name | Path1 |

Date of creation | 2013-03-22 12:16:49 |

Last modified on | 2013-03-22 12:16:49 |

Owner | CWoo (3771) |

Last modified by | CWoo (3771) |

Numerical id | 8 |

Author | CWoo (3771) |

Entry type | Definition |

Classification | msc 05C38 |

Related topic | ClosedPath |

Defines | path length |