The Probability of Connectedness of an Unlabelled Graph Can Be Less for More Edges

We write <!-- MATH $\beta = \beta (n,q)$ --> for the probability that a graph on n unlabelled nodes with q edges is connected; that is is the ratio of the number of connected graphs to the total number of graphs. We write <!-- MATH $N = n(n - 1)/2$ --> . For fixed n we might expect that would increase with q, at least nonstrictly. On the contrary, we show that, for any given integer s, we have <!-- MATH $\beta (n,q + 1) < \beta (n,q)$ --> <img width="183" height="41" align="MIDDLE" border="0" src="images/img5.gif" alt="$ \beta (n,q + 1) < \beta (n,q)$"> for <!-- MATH $N - n - s \leqq q \leqq N - n$ --> and <!-- MATH $n > {n_0}(s)$ --> {n_0}(s)$">. We can show that <!-- MATH $\beta (n,q + 1) < \beta (n,q)$ --> <img width="183" height="41" align="MIDDLE" border="0" src="images/img8.gif" alt="$ \beta (n,q + 1) < \beta (n,q)$"> for a much longer range, but this requires much more elaborate arguments.