Connectivity for Bridge-Addable Monotone Graph Classes
A class of labelled graphs is bridge-addable if, for all graphs G in 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 ; the class is monotone if, for all G ∈ and all subgraphs H of G , we have H ∈ . We show that for any bridge-addable, monotone class whose elements have vertex set {1,. . ., n }, the probability that a graph chosen uniformly at random from is connected is at least (1− o n (1)) e −½ , where o n (1) → 0 as n → ∞. This establishes the special case of the conjecture of McDiarmid, Steger and Welsh when the condition of monotonicity is added. This result has also been obtained independently by Kang and Panagiotou.