# Reference for “almost all graphs have diameter 2”

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.

-

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...

-
The introductory paragraph of a 1981 TAMS paper by Bollobas available at ams.org/journals/tran/1981-267-01/S0002-9947-1981-0621971-7/… supports the likely Moon-Moser origin. Also, an author search on "e.n. gilbert" at projecteuclid.org will produce his "Random Graphs" article. –  Barry Cipra Dec 3 '12 at 17:57
I checked the Moon Moser paper, that is indeed your reference. I've emailed you a somewhat crappy but legible scan of the paper. –  Louigi Addario-Berry Dec 3 '12 at 19:59

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.

-
The four Russians are Y.V. Glebskii, D.I. Kogan, M.I. Liogon'kii, and V.A. Talanov. The paper is "Range and degree of realizability of formulas in the restricted predicate calculus" [Kibernetika (Kiev) 1969, no.2, 17-28; translation in Cybenetics (Kiev) 5 (1969) 142-154]. I've been told that this paper is rather difficult to read. –  Andreas Blass Dec 3 '12 at 13:58
Thanks! I actually know this derivation, but I wanted a encapsulated reference to this precise fact. –  Felix Goldberg Dec 3 '12 at 14:03