Abstract
A class of labelled graphs isbridge-addableif, for all graphsGin and all verticesuandvin distinct connected components ofG, the graph obtained by adding an edge betweenuandvis also in ; the class ismonotoneif, for allG∈ and all subgraphsHofG, we haveH∈ . 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−on(1))e−½, whereon(1) → 0 asn→ ∞. 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.

This publication has 15 references indexed in Scilit: