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(-1/2) + o(1) when n tends to infinity. This lower bound is asymptotically best possible since it is reached for forests.