The distance between connected vertices is the least length of a path joining them.
The closed graph ball of radius centered at vertex is
where is shortest-path distance. In an unweighted graph, distances count edges, so a noninteger radius gives the same set as its integer part. Vertices in other connected components have infinite distance and lie outside every finite-radius ball.
For the path , and is the whole vertex set. The sphere at radius one contains only ; a ball also contains its center and all smaller distances.
A graph ball is first a vertex set. If one wants a graph on those vertices, the induced subgraph convention must be specified. Ball growth, such as how changes with , records large-scale connectivity beyond the immediate vertex degree.
The average shortest path length averages graph distances over distinct ordered pairs of vertices. A nodal value averages distances from one specified vertex to all others. Disconnected pairs require a separate convention.
Given positive edge lengths on a graph, define the distance between two vertices by
where ranges over finite graph paths. An absent path gives distance . On a finite connected graph, this is a metric: reversing and concatenating routes gives symmetry and the triangle inequality, while the least edge length bounds every nonempty path away from zero. It is also a metric on a connected locally finite graph, since every path leaving a fixed vertex pays at least the positive minimum of its finitely many incident edge lengths.
Positive edge lengths alone do not guarantee a metric on an arbitrary infinite graph. Join two vertices through intermediate vertices , with both edges having length . Then for every , so distinct vertices have distance zero. On each finite-distance component the general construction is a pseudometric; its zero-distance classes give a metric quotient.
The diameter of a connected finite graph is the maximum distance between two vertices.
Thus diameter is an extremal statistic of graph distance.
If a connected graph has adjacency matrix and diameter , then
are linearly independent. For the largest index with a nonzero coefficient, choose vertices at distance ; the corresponding entries of all lower powers vanish, while by the walk count from powers of an adjacency matrix.

Articles by others on the same topic (1)

In graph theory, the **distance** between two vertices (or nodes) in a graph is defined as the length of the shortest path connecting them. The length of a path is typically measured by the number of edges it contains. Therefore, the distance \( d(u, v) \) between two vertices \( u \) and \( v \) is the minimum number of edges that need to be traversed to get from \( u \) to \( v \).