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)$.