As proved by Karger [1]}, \(D\)  has size \(\widetilde{O}(cn/P)\)  with high probability. Thorup [2]} generalizes this by proving that \(D\)  undergoes only \(\widetilde{O}(cn/P)\)  insertions
throughout any sequence of edge deletions to \(S\) .
Since \(D\)  depends only on the \(c\) -edge-connected components of \(S\) , it is enough to have a \(c\) -certificate of \(S\)  in order to define \(D\) . Hence, a \(c\) -certificate
of \(S\)  (which is a graph a size \(O(mP)\) , i.e., a constant factor smaller) is maintained under edge deletions recursively. The recursion stops when the size
of the input graph is \(O(cn)\) .
To maintain \(D\)  at each recursive level, we first need to maintain
the \(c\) -edge-connected components of the (recursive) certificate of \(S\)  under edge deletions.
The certificate of \(S\)  can be (inductively) seen to have \(\widetilde{O}(cn/P)\)  edges and
undergo \(\widetilde{O}(cn/P)\)  updates. As a result, for \(P =1/2\)  maintaining its \(c\) -edge-connected components costs
\(\widetilde{O}(cn\cdot T_c(n))\)  total time using the fully-dynamic \(c\) -edge-cut data structure.
Since at each recursion level the certificate size decreases geometrically, the expected cost of all
the dynamic \(c\) -edge-cut data structures is \(\widetilde{O}(cn\cdot T_c(n))\) .
