Connectivity for bridge-alterable graph classes

© 2016 Elsevier Ltd. A collection A of graphs is called bridge-alterable if, for each graph G with a bridge e, G is in A if and only if G-e is. For example the class F of forests is bridge-alterable. For a random forest F n sampled uniformly from the set Fn of forests on vertex set (1,...,n), a classical result of Rényi (1959) shows that the probability that F n 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 A, for a random graph R n sampled uniformly from the graphs in A on (1,...,n), the probability that R n 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 R n is connected is at least the minimum over 25n < t≤n of the probability that F t is connected.