MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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

share|cite|improve this answer
The introductory paragraph of a 1981 TAMS paper by Bollobas available at… supports the likely Moon-Moser origin. Also, an author search on "e.n. gilbert" at 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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.