- #1

- 193

- 1

## Main Question or Discussion Point

I am thinking about this problem that come up in some of my work, I think this has been solved before, though I am not aware where I could find the solution. Here is the question:

Suppose a graph has say 20 nodes with no edge initially, and at each instance, 4 (different) nodes are randomly drawn with equal probability and all 6 edges among them are added to the graph. How do I estimate the expected number of iterations before the graph become connected (just connected, no need to be completed)? Thanks.

Suppose a graph has say 20 nodes with no edge initially, and at each instance, 4 (different) nodes are randomly drawn with equal probability and all 6 edges among them are added to the graph. How do I estimate the expected number of iterations before the graph become connected (just connected, no need to be completed)? Thanks.