How many edges before a random graph is connected?
A classical result of Erdős and Rényi states that if $k = \frac{n}{2} (\log n + c)$, then as $n\to\infty$, the probability that the graph is connected tends to $e^{-e^{-c}}$. You can find the proof in any textbook on random graphs.