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

Guillaume Chapuy, Guillem Perarnau

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
95 Downloads (Pure)


A class of graphs is \emph{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.
Original languageEnglish
JournalJournal of Combinatorial Theory. Series B
Early online date17 Sept 2018
Publication statusE-pub ahead of print - 17 Sept 2018


  • bridge-addable classes
  • random graphs
  • random forests
  • connectivity


Dive into the research topics of 'Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture'. Together they form a unique fingerprint.

Cite this