Path graph

Example

Let $n \ge 1$ be an integer. The path graph $P_n$ is the graph 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, 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.