A diameter graph of a finite set of at least two points in Euclidean space is the simple graph with vertex set in which two distinct vertices are adjacent iff their Euclidean distance is the generalized diameter of (Graham 1975, p. 166). The graph diameter is a different quantity defined using graph distance.

For the vertex set of a regular polygon with an odd number of sides, the diameter graph is the cycle graph . For an even number of sides, it is the graph disjoint union of copies of the complete graph , joining opposite vertices. Indeed, the longest chords advance steps around the odd polygon and steps around the even polygon.

Diameter graphs record the distance constraints attained with equality in the biggest little polygon problem, where the polygon diameter is fixed and the area is maximized.

Brass et al. (2005, p. 231) asked whether deleting a bounded number of vertices from a diameter graph in suffices to leave a 3-colorable induced subgraph. Lopez-Campos (2026) proved that deleting at most one graph vertex suffices. The edges in this subgraph are inherited from the original diameter graph.

Lopez-Campos (2026) also showed that for every positive integer there is a finite set for which every subset of smaller generalized diameter has fewer than points. This construction uses a diameter graph realization theorem of Damásdi (2026) that Lopez-Campos identifies as under review.

See also

Biggest Little Polygon, Generalized Diameter, Polygon Diameter

Explore with Wolfram|Alpha

References

Brass, P.; Moser, W.; and Pach, J. Research Problems in Discrete Geometry. New York: Springer-Verlag, 2005. https://doi.org/10.1007/0-387-29929-7.Damásdi, G. "Geometric Realizations with Strong Self-Duality Part II: Diameter Graphs, Reuleaux Polyhedra, and Thrackles." 5 Oct 2026. https://arxiv.org/abs/2610.06340.Foster, J. and Szabó, T. "Diameter Graphs of Polygons and the Proof of a Conjecture of Graham." J. Combin. Th. Ser. A 114, 1515-1525, 2007. https://doi.org/10.1016/j.jcta.2007.02.006.Graham, R. L. "The Largest Small Hexagon." J. Combin. Th. Ser. A 18, 165-170, 1975. https://doi.org/10.1016/0097-3165(75)90004-7.Lopez-Campos, G. "On Diameter Graphs Problems: A Proof of Brass's Conjecture." 3 Nov 2026. https://arxiv.org/abs/2611.05631v1.

Cite this as:

Weisstein, Eric W. "Diameter Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/DiameterGraph.html

Subject classifications