Let $G$ be a undirected graph with $n$ vertices and no edges, and let $f(k)$ be the probability that if we add $k$ edges randomly to $G$ that $G$ will be connected. How would one determine $f(k)$ for a given $n\in\mathbb N$?


When we add an edge to the graph $G$, any edge that can exist would be equally likely to be added. We can not add the same edge twice, so when $k=\frac{n^2+n}2$ (the number of possible edges in a graph with $n$ verticies), then $f(k)=1$.

Definition for connected may be found on wikipedia.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.