Reference for "almost all graphs have diameter 2" - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T23:26:50Z http://mathoverflow.net/feeds/question/115276 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/115276/reference-for-almost-all-graphs-have-diameter-2 Reference for "almost all graphs have diameter 2" Felix Goldberg 2012-12-03T11:42:15Z 2012-12-03T14:10:03Z <p>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 <em>Graphs &amp; Digraphs</em> 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. </p> http://mathoverflow.net/questions/115276/reference-for-almost-all-graphs-have-diameter-2/115292#115292 Answer by Andreas Blass for Reference for "almost all graphs have diameter 2" Andreas Blass 2012-12-03T13:48:45Z 2012-12-03T13:55:08Z <p>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.</p> http://mathoverflow.net/questions/115276/reference-for-almost-all-graphs-have-diameter-2/115296#115296 Answer by Brendan McKay for Reference for "almost all graphs have diameter 2" Brendan McKay 2012-12-03T14:00:40Z 2012-12-03T14:10:03Z <p>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.</p> <p>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.</p> <p>I guess the Gilbert mentioned is Gilbert, E. N. Random graphs. Ann. Math. Statist. 30 (1959) 1141–1144. It isn't clear exactly why... </p>