# Removing edges from Erdős–Rényi graph to make two nodes disconnected

Consider a Erdős–Rényi graph on $n$ nodes, say $1,2,\ldots,n$, ($n\geq 3$) such that the probability of edge between any two nodes is $c/n$. I wish to know if there is a result that says

"There exists $a$ edges such that if they are removed, nodes $1$ and $2$ get disconnected with high probability (as $n\rightarrow \infty$), i.e., there are no paths left between nodes $1$ and $2$".

for cases $c=\ln n, (\ln n)^2$. In particular, I am interested in the least possible value (or scaling) of $a$.

For example, one way of disconnecting nodes $1$ and $2$ is to isolate node $1$ from its neighbors. Since $c>1$, the maximum degree of node $1$ is bounded above by $2\ln n/\ln\ln n$ with high probability as $n\rightarrow \infty$ (this is a known result). So, we can say that the minimum value of $a$ is less than $2\ln n/\ln\ln n$ or it scales as $O(\ln n/\ln\ln n)$.

• I'm not sure if you have "with high probability" in the right place. You want that the disconnecting edges exist with high probability, not that 1 and 2 are disconnected with high probability, right? – Brendan McKay May 21 '13 at 14:16
• You seem to be saying that if $c = \ln n$, then the maximum degree is going to be at most $2 \ln n / \ln \ln n$. I guess that's not the case? – Andrew D. King May 21 '13 at 15:35
• There is more than one thing wrong with that statement about the degree of node $1$. It's conceivable that the mean would be higher than a high probability bound, but not here. I think that is a highly garbled version of the maximum of $n$ IID normals being about $c \log \log n$ standard deviations above the mean, though I think the standard deviation is $\sqrt{\log n}$ (as Poisson dist.). Second, why would you be looking at the maximum degree of a vertex of the graph, instead of just the greater of the degrees of nodes $1$ and $2$? So you can drop the $\log \log n$. – Douglas Zare May 21 '13 at 21:50
• I think the maximum degree is a red herring. For example, when $c<1$ is constant you can easily check that the probability of having two edge-disjoint paths from 1 to 2 goes to zero, whereas the probability of one of them having degree 0 or 1 does not go to 1. So with high probability they can be separated by removing one edge even though there is some non-zero probability both have degree 2. The same holds for $c=1$, but larger $c$ is harder. I'm pretty sure this has all been worked out, but I'm too lazy to search. – Brendan McKay May 22 '13 at 2:30
• I don't think the degree is a red herring. I think for large $c$, the easiest way to disconnect $1$ from $2$ is likely to be by eliminating all of the edges around $1$ or around $2$. – Douglas Zare May 22 '13 at 3:47