Connectivity of addable graph classes

A non-empty class A of labeled graphs is weakly addable if for each graph G∈A and any two distinct components of G, any graph that can be obtained by adding an edge between the two components is also in A. For a weakly addable graph class A, we consider a random element Rn chosen uniformly from the set of all graphs in A on the vertex set {1,…,n}. McDiarmid, Steger and Welsh conjecture that the probability that Rn is connected is at least e−1/2+o(1) as n→∞, and showed that it is at least e−1 for all n [C. McDiarmid, A. Steger, D.J.A. Welsh, Random graphs from planar and other addable classes, in: M. Klazar, J. Kratochvil, M. Loebl, J. Matousek, R. Thomas, P. Valtr (Eds.), Topics in Discrete Mathematics, Dedicated to Jarik Nešetril on the occasion of his 60th birthday, Algorithms Combin., vol. 26, Springer-Verlag, Berlin, 2006, pp. 231–246]. We improve the result, and show that this probability is at least e−0.7983 for sufficiently large n. We also consider 2-addable graph classes B where for each graph G∈B and for any two distinct components of G, the graphs that can be obtained by adding at most 2 edges between the components are in B. We show that a random element of a 2-addable graph class on n vertices is connected with probability tending to 1 as n tends to infinity.