Distance in a graph

Definition

Let $G$ be a graph and let $u, v$ be vertices of $G$. If $v$ is reachable from $u$, the distance $d(u, v)$ is the smallest length of a walk from $u$ to $v$. If $v$ is not reachable from $u$, then $d(u, v) = \infty$.

Remarks

A shortest walk is a path, so $d(u, v)$ is also the smallest length of a path. Such a path is a geodesic. On a connected graph, $d$ is a metric: $d(u, v) = 0$ only for $u = v$, it is symmetric, and it satisfies the triangle inequality.

Explanations

L1 human

The distance between two vertices is the smallest number of edges that you must cross to go from one to the other. In the cycle $C_6$, opposite vertices have distance $3$.