Connectivity of Addable Monotone Graph Classes

A class A of labelled graphs is weakly addable if if for all graphs G in A and all vertices u and v in distinct connected components of G, the graph obtained by adding an edge between u and v is also in A; the class A is monotone if for all G ∈ A and all subgraphs H of G, we have H ∈ A. We show that for any weakly addable, monotone class A whose elements have vertex set {1,..., n}, the probability that a uniformly random element of A is connected is at least (1 − on(1))e −0.540760, where on(1) → 0 as n →∞. Furthermore, if every element of A has girth at least g> 1, then the probability that A is connected is at least (1 − og(1)))e −1/2. The latter result establishes a conjecture of McDiarmid et al. (2006) for graphs of large girth