  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 $\mathcal{G}_n$ is any bridge-addable class of graphs on $n$
vertices, and $G_n$ is taken uniformly at random from $\mathcal{G}_n$, then
$G_n$ is connected with probability at least $e^{-\frac{1}{2}} + 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.
