The probability of connectedness of an unlabelled graph can be less for more edges
Elizabeth Mary Wright · Proceedings of the American Mathematical Society · 1972
We write β = β ( n , q ) \beta = \beta (n,q) for the probability that a graph on n unlabelled nodes with q edges is connected; that is β \beta is the ratio of the number of connected graphs to the total number of graphs. We write N = n ( n − 1 ) / 2 N = n(n - 1)/2 . For fixed n we might expect that β \beta would increase with q , at least nonstrictly. On the contrary, we show that, for any given integer s , we have β ( n , q + 1 ) > β ( n , q ) \beta (n,q + 1) > \beta (n,q) for N − n − s ≦ q ≦ N − n N - n - s \leqq q \leqq N - n and n > n 0 ( s ) n > {n_0}(s) . We can show that β ( n , q + 1 ) > β ( n , q ) \beta (n,q + 1) > \beta (n,q)