# Disconnecting a complete graph by removing edges randomly

Given a complete graph with $n$ nodes, I remove edges randomly with probability $p$ such that I want to disconnect the graph.

I want to find out the minimum number of edges that I must remove randomly to disconnect the graph. Also the value of $p$ where I can disconnect the graph by removing the least number of edges.

• What research have you done? – Yuval Filmus Nov 12 '14 at 4:00
• This is just the standard Erdős–Rényi $G(n,p)$ model, except that, by starting with a complete graph and deleting edges, you're looking at $G(n,1-p)$. – David Richerby Nov 12 '14 at 8:25
• Minimum number is denitely $n$, are you looking for the estimated number of edges that need to be removed? – orezvani Nov 13 '14 at 0:19

For your first question, an empty graph becomes connected roughly when $n\log n$ random edges are inserted into it, in a way quantified in Erdős and Rényi's fundamental paper On the evolution of random graphs, and recounted in textbooks on random graphs.