Course contentsShow
← Mathematics
Lesson 2660 of 3,12153. Graph TheoryFree lesson

Distance and Diameter

Define distance between vertices; calculate shortest path lengths and determine the diameter of a graph.

Distance and Diameter

You'll learn: How to measure the shortest separation between any two vertices in a graph and find the maximum such distance across the entire graph.

What Is Distance Between Vertices?

In graph theory, the distance between two vertices is the length (number of edges) of the shortest path connecting them. Think of it like finding the quickest route between two cities on a map—you want the fewest roads to travel.

If vertices u and v are in the same connected component, we denote their distance as d(u, v). If no path exists between them (they're in different components), the distance is considered infinite or undefined.

Example

In a graph where vertex A connects to B, B connects to C, and C connects to D:

  • d(A, B) = 1 (directly connected)
  • d(A, C) = 2 (path A → B → C)
  • d(A, D) = 3 (path A → B → C → D)

What Is the Diameter?

The diameter of a connected graph is the maximum distance between any pair of vertices. It tells you the longest "shortest path" you might encounter—the worst-case separation in your graph.

To find the diameter:

  1. Calculate d(u, v) for every pair of vertices u and v
  2. The diameter is the largest of these distances

Example Continued

If our graph has vertices {A, B, C, D} arranged in a line, the diameter is d(A, D) = 3 because no other pair is farther apart via their shortest paths.

For disconnected graphs, the diameter is typically undefined or infinite.

Key Takeaway: Distance measures the shortest path length between two vertices; diameter is the greatest distance between any vertex pair in a connected graph.