# Why is the diameter of a random graph important?

I can see the diameter of a graph, defined as the length of the longest shortest path, is a non-trivial quantity in a random graph e.g. the random graph $$G(n,p)$$ formed by adding edges between $$n$$ points independently with probability $$p$$.

But what makes it so mathematically significant? What relations does it have to the other fundamental graph ideas? Moreover, if I add some constraint on the graph, such as the degree distribution, or spatial constraints on the vertices (i.e. random geometric graph), what does this do to the significance of the graph diameter?

• It's primarily important because the diameters of graphs are important. Aug 17 '20 at 12:26
• What are the key ideas behind the significance of the graph diameter?
– apkg
Aug 17 '20 at 12:35

Graph diameter is significant in its own right, in the same way the chromatic number or maximum degree is. If you want your graph to model a network, it tells you the maximum number of 'hops' that one has to take to get from one node to any other. If your graph is embedded geometrically as, say, a graph where each edge is a straight line of length 1, then the diameter of the (abstract) graph is an upper bound on the diameter of the embedded graph, considered as a subset of $$\mathbb{R}^n$$.
Let $$D$$ be the diameter of a graph, $$n$$ its order, $$\Delta$$ its maximum degree and $$\kappa$$ its connectivity. Some general heuristics for how diameter behaves (these are trends, not theorems):
• In a similar vein to the above points, the diameter and maximum degree together bound the total number of vertices a graph can have. Heuristically, you can't get more vertices out of a graph than if you create a tree of depth $$D$$ that branches out roughly $$\Delta-1$$ times at each layer, with a few extra edges to close things up. Studying this bound is the topic of the degree diameter problem.
• While the diameter and maximum degree bound $$n$$ from above, the diameter and connectivity bound it from below. The bound looks roughly like $$n \geq \kappa \cdot (D-1)$$.