# Distance (graph theory)

In the mathematical field of graph theory, the **distance** between two vertices in a graph is the number of edges in a shortest path (also called a **graph geodesic**) connecting them. This is also known as the **geodesic distance**.^{[1]} Notice that there may be more than one shortest path between two vertices.^{[2]} If there is no path connecting the two vertices, i.e., if they belong to different connected components, then conventionally the distance is defined as infinite.

A metric space defined over a set of points in terms of distances in a graph defined over the set is called a **graph metric**.
The vertex set (of an undirected graph) and the distance function form a metric space, if and only if the graph is connected.

The partition of a graph's vertices into subsets by their distances from a given starting vertex is called the level structure of the graph.

A graph such that for every pair of vertices there is a unique shortest path connecting them is called a geodetic graph. For example, all trees are geodetic.^{[4]}

Often peripheral sparse matrix algorithms need a starting vertex with a high eccentricity. A peripheral vertex would be perfect, but is often hard to calculate. In most circumstances a pseudo-peripheral vertex can be used. A pseudo-peripheral vertex can easily be found with the following algorithm: