Connectivity in bridge-addable graph classes: The McDiarmid–Steger–Welsh conjecture

A class of graphs is bridge-addable if given a graph G in the class, any graph obtained by adding an edge between two connected components of G is also in the class. We prove a conjecture of McDiarmid, Steger, and Welsh, that says that if G _n is any bridge-addable class of graphs on n vertices, and G _n is taken uniformly at random from G _n , then G _n is connected with probability at least e ^{−[Formula presented]} +o(1), when n tends to infinity. This lower bound is asymptotically best possible since it is reached for forests. Our proof uses a “local double counting” strategy that may be of independent interest, and that enables us to compare the size of two sets of combinatorial objects by solving a related multivariate optimization problem. In our case, the optimization problem deals with partition functions of trees relative to a supermultiplicative functional.