Estimation for a Graph Theory problem

[chingkui]

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.

 

[Zula110100100]

I feel that I should include I am not an expert by any means, but here is how I would approach it.

So all you really need is the 20 nodes and 4 picked each time right, I think the graph will be connected once every node is picked once regardless of the extra 2 edges they don't matter, I don't know the answer, but I think the question could be asked "Picking 4 at a time, how long does it take for all 20 to be picked at random?" I guess one answer is that the number of rounds lies in the interval [5,∞).
The chance goes up with every round, with a minimal chance of 5!/(5^5) = 3.84%

for the 5 rounds to work, you have to get unpicked nodes every round and you'd have a first round with a 20/20 chance of getting an unpicked node, second round, 16/20 chance of getting an unpicked node,3rd 12/20 and so on, which reduces to 5/5,4/5,3/5,2/5,1/5, from which you get the above. How you would figure the chances if it didn't go perfect I am not sure of, sorry.

 

[Zula110100100]

And actually that is bad, each round would break into the 4 individual draws? So you'd have 1*16/20*15/19*14/18*13/17*12/20*11/19...

so: [itex] \frac{20!}{(20^5)(19^5)(18^5)(17^5)} =\frac{20!}{(\frac{20!}{16!})^5} = .000000114 = .0000114% [/itex]% chance as a minimum?