Connectivity for bridge-alterable graph classes

A collection AA of graphs is called bridge-alterable if, for each graph GG with a bridge ee, GG is in AA if and only if G−eG−e is. For example the class FF of forests is bridge-alterable. For a random forest FnFn sampled uniformly from the set FnFn of forests on vertex set {1,…,n}{1,…,n}, a classical result of Rényi (1959) shows that the probability that FnFn is connected is e−12+o(1).Recently Addario-Berry et al. (2012) and Kang and Panagiotou (2013) independently proved that, given a bridge-alterable class AA, for a random graph RnRn sampled uniformly from the graphs in AA on {1,…,n}{1,…,n}, the probability that RnRn is connected is at least e−12+o(1). Here we give a more straightforward proof, and obtain a stronger non-asymptotic form of this result, which compares the probability to that for a random forest. We see that the probability that RnRn is connected is at least the minimum over 25n