I am researching connectivity in sampled subgraphs and have come across the following problem.
A bridge between two vertices $a$ and $b$ of a graph $G$ is an edge $e$ such that removing $e$ from $G$ disconnects $a$ and $b$. Note that $e$ is not a bridge if $a$ and $b$ are not connected in $G$. Denote by $B_G(a, b)$ the number of bridges between $a$ and $b$.
I am interested in how the number of bridges between $a$ and $b$ asymptotically distributes when sampling a random subgraph of $G$. More concretely, let $G=(V, E)$ be a graph on $n$ vertices, possibly with multiple edges. Now, sample each edge of $G$ independently with probability 1/2, yielding a new graph $G'$.
My question is: Is there a non-trivial function $g(n)$ and an $\ell>0$ such that $$P(\forall a, b\in V(G)\colon B_{G'}(a, b)<g(n))>1-n^{-\ell}$$ for every choice of base graph $G$?
One example to note is the following. Sample the graph $G$ from $\mathcal G_{n, \frac 2n}$, i.e., the complete graph where each edge is sampled with probability $2/n$. Then the sampled subgraph $G'$ og $G$ is distributed according to $\mathcal G_{n, \frac1n}$. The latter has components of size $\Theta(n^{2/3})$ and I believe that each such component is fairly tree-like of diameter $\Theta(n^{1/3})$. In that case, this shows that we must have $g(n)= \Omega(n^{1/3})$.
