Reference for "almost all graphs have diameter 2" - MathOverflow

Reference for "almost all graphs have diameter 2"

2012-12-03T11:42:15Z

The property in the title is well-known. I am trying to find an original reference to its first appearance in print. The 4th edition of Graphs & Digraphs by Chartrand and Lesniak lists this as Theorem 13.6 and says that it's a generalization of a result by Gilbert, but gives no further reference.

Answer by Andreas Blass for Reference for "almost all graphs have diameter 2"

2012-12-03T13:48:45Z

The result you asked about follows instantly from Fagin's proof of the zero-one law for finite graphs. He shows that all of Gaifman's extension axioms have asymptotic probability 1, and "diameter $\leq 2$" is essentially one of the extension axioms. Fagin's paper is "Probabilities on finite models" [J. Symbolic Logic 41 (1976) pp.50-58]. I believe the zero-one law was proved earlier by four Russians, but I don't have access to their paper and don't know whether their method immediately implies the "diameter $\leq2$" result.

Answer by Brendan McKay for Reference for "almost all graphs have diameter 2"

2012-12-03T14:00:40Z

I think you will find it in Moon, J. W.; Moser, L. Almost all (0,1) matrices are primitive. Studia Sci. Math. Hungar. 1 (1966) 153–156. But I don't have time to visit the library to be sure and I don't see it online.

It is certainly in Burtin, Ju. D. Asymptotic estimates of the diameter and the independence and domination numbers of a random graph. (Russian) Dokl. Akad. Nauk SSSR 209 (1973), 765–768.

I guess the Gilbert mentioned is Gilbert, E. N. Random graphs. Ann. Math. Statist. 30 (1959) 1141–1144. It isn't clear exactly why...