Finally, dealing with item (2) is less straightforward.
This is because in the analysis of the data structure of [1]}, Thorup invokes a result due to Karger [2]} saying that
if a graph \(G\)  is \(c^{\prime }\) -edge-connected graph,
where \(c^{\prime }=\Omega ((c+\log {n})/p^{\prime })\) , and \(p^{\prime }\in (0,1)\) 
then \(G(p^{\prime })\)  is \(c\) -edge-connected with high probability (depending on the constant hidden in the \(\Omega \)  notation).
This is then used to show that the number of
edges between different \(c\) -edge-connected components of a certificate (which is \(G(p^{\prime })\)  augmented with the edges of \(G\)  connecting distinct \(c\) -edge-connected components of \(G(p)\)  , where \(p^{\prime }\)  is any constant less than 1)
that Thorup uses is \(O(c^{\prime }n)\)  with high probability. This is where the \(c+\log {n}\)  term in the bounds in Theorem REF  comes from.
Unfortunately, roughly speaking, Karger's proof
applies a Chernoff bound to an exponential number of cuts in \(G\)  and therefore requires sampling with full independence, i.e., \(\Theta (m)\)  random bits.
