Universal diameter bounds for random graphs with given degrees

Given a graph G, let diam(G) be the greatest distance between any two vertices of G which lie in the same connected component, and let diam⁺(G) be the greatest distance between any two vertices of G; so diam⁺(G)=∞ if G is not connected. Fix a sequence (d₁,…,dₙ) of positive integers, and let G be a uniformly random connected simple graph with V(G)=[n]:=\1,…,n\ such that degG(v)=dᵥ for all v ∈ [n]. We show that, unless a $1-o(1)$ proportion of vertices have degree $2$, then E[diam(G)]=O(√n). It is not hard to see that this bound is best possible for general degree sequences (and in particular in the case of trees, in which ∑ᵥ₌₁ⁿ dᵥ = 2(n-1)). We also prove that this bound holds without the connectivity constraint. As a key input to the proofs, we show that graphs with minimum degree $3$ are with high probability connected and have logarithmic diameter: if min(d₁,…,dₙ) ≥ 3 then diam⁺(G)=OP(log n); this bound is also best possible.