Reference articles on history, science, culture and more
Surprise meSurprise meSubscribe
Encyclopedia

Diameter (graph theory)

Longest distance between two vertices

Wikipedia contributorsAdapted for Fathomly · View authors
2 min read
Source updated June 24, 2026
Image credit is listed at the end of this article.

In graph theory, the diameter of a connected undirected graph is the farthest distance between any two of its vertices. That is, it is the diameter of a set for the set of vertices of the graph, and for the shortest-path distance in the graph. Diameter may be considered either for weighted or for unweighted graphs. Researchers have studied the problem of computing the diameter, both in arbitrary graphs and in special classes of graphs.

The diameter of a disconnected graph may be defined to be infinite, or undefined.

01Graphs of low diameter

The degree diameter problem seeks tight relations between the diameter, number of vertices, and degree of a graph. One way of formulating it is to ask for the largest graph with given bounds on its degree and diameter. For any fixed degree, this maximum size is exponential in diameter, with the base of the exponent depending on the degree.

The girth of a graph, the length of its shortest cycle, can be at most 2k+1 for a graph of diameter k. The regular graphs for which the girth is exactly 2k+1 are the Moore graphs. Only finitely many Moore graphs exist, but their exact number is unknown. They provide the solutions to the degree diameter problem for their degree and diameter.

Small-world networks are a class of graphs with low diameter, modeling the real-world phenomenon of six degrees of separation in social networks.

02Algorithms

In arbitrary graphs

The diameter of a graph can be computed by using a shortest path algorithm to compute shortest paths between all pairs of vertices, and then taking the maximum of the distances that it computes. For instance, in a graph with positive edge weights, this can be done by repeatedly using Dijkstra's algorithm, once for each possible starting vertex. In a graph with n vertices and m edges, this takes time O(mn+n^{2}\log n). Computing all-pairs shortest paths is the fastest known method for computing the diameter of a weighted graph exactly.

In an unweighted graph, Dijkstra's algorithm may be replaced by a breadth-first search, giving time O(mn). Alternatively, the diameter may be computed using an algorithm based on fast matrix multiplication, in time proportional to the time for multiplying n\times n matrices, approximately O(n^{2.37}) using known matrix multiplication algorithms. For sparse graphs, with few edges, repeated breadth-first search is faster than matrix multiplication. Assuming the strong exponential time hypothesis, repeated breadth-first search is near-optimal: this hypothesis implies that no algorithm can achieve time O(m^{2-\varepsilon }) for any \varepsilon >0.

It is possible to approximate the diameter of a weighted graph to within an approximation ratio of 3/2, in time {\tilde {O}}(\min(m^{3/2},mn^{2/3}), where the {\tilde {O}} notation hides logarithmic factors in the time bound. Under the strong exponential time hypothesis, no substantially more accurate approximation, substantially faster than all pairs shortest paths, is possible.

In special classes of graphs

The diameter can be computed in linear time for interval graphs, and in near-linear time for graphs of bounded treewidth. In median graphs, the diameter can be found in the subquadratic time bound {\tilde {O}}(n^{1.6456}). In any class of graphs closed under graph minors, such as the planar graphs, it is possible to compute the diameter in subquadratic time, with an exponent depending on the graph family.

Watch videos about Diameter (graph theory)Explainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Diameter (graph theory)”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Images, from Wikimedia Commons:

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Continue exploring

Related topics

Triameter (graph theory)

In graph theory, the triameter is a metric invariant that generalizes the concept of a graph's diameter. It is defined as the maximum sum of pairwise distances between any three vertices in a connected graph G {\textstyle G} and is denoted by where V {\textstyle V} is the vertex set of G {\textstyle G} and d {\textstyle d(u,v)} is the length of the shortest path between vertices u {\textstyle u} and v {\textstyle v} .

Diameter (group theory)

In the area of abstract algebra known as group theory, the diameter of a finite group is a measure of its complexity. Consider a finite group {\displaystyle \left(G,\circ \right)} , and any set of generators S. Define D S {\displaystyle D_{S}} to be the graph diameter of the Cayley graph Λ = ( G , S ) {\displaystyle \Lambda =\left(G,S\right)} .

Cayley graph

In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group, is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem, and uses a specified set of generators for the group.