Question

If there are n vertices and each pair of them is connected by an edge with probability p, what is the probability that the resulting graph is connected?

Answer 1

The probability that a graph is connected depends on the value of n and p. For example, when n = 2, the graph is always connected, and when n = 3 and p = 1, the graph is also connected. In general, the probability of a graph being connected can be calculated using the Erdős–Rényi theorem, which states that the probability of a graph being connected is 1 - (1 - p)^(n(n-1)/2).

Explanation: