---
tag: 075WR6W3Y3
kind: example
name: Path graph
msc: [05C38]
instance_of: [00C0BR7D7H]
sources:
  - url: https://en.wikipedia.org/wiki/Path_graph
    locator: lead section
same_as:
  wikidata: Q917421
  wikipedia: Path graph
---

## Example

Let $n \ge 1$ be an integer.
The path graph $P_n$ is the [[graph|0JD5C82QMB]] with vertex set $\{0, 1, \dots, n - 1\}$ in which $i$ and $j$ are adjacent if and only if $|i - j| = 1$.

## Remarks

$P_n$ has $n$ vertices and $n - 1$ edges. It is a [[tree|0MJ0JS72DZ]], and for $n \ge 2$ it has exactly two leaves, $0$ and $n - 1$.
Some authors write $P_n$ for the path with $n$ edges, that is, with $n + 1$ vertices.

## Explanations

### L1 human

A path graph is a row of vertices, each joined to the next.
It looks like beads on a string.