Connectivity of addable graph classes (Q2483480)

A non-empty class \(A\) of labeled graphs is weakly addable if the class is closed under the joining of an edge between any two distinct components in a graph of the class. Consider a non-empty subclass of \(A\) containing the graphs of \(n\) specified vertices. For sufficiently large \(n\), a new lower bound is given for the probability that a graph drawn uniformly at random from the subclass is connected. By extending the notion of addability to closeness under the addition of at most two edges between any two distinct components of a graph, it is proved that the random graph is connected with probability 1 as \(n\) tends to infinity.