It turns out very challenging to get rid of the \(O(m\log (n^2/m))\)  term associated with finding cuts when components split in Thorup's reduction. If we knew that all of these cuts were small, say of size at most \(\delta \) , then we could apply a whole bag of tricks for efficiently finding them in a total time of \(\tilde{O}(n\delta )\) , e.g., using invertible Bloom lookup tables [1]}, or the XOR-trick [2]}, [3]}, [4]}. Unfortunately, the bound of \(\tilde{O}(cn/P)\)  only gives an average bound on the number of edges between pairs of components, and in fact there can be pairs of components having as many as \(\Omega (n^{1/3})\)  edges between them, as we will later show. In order to resolve this, we have to introduce a new type of sample based \(c\) -edge certificate obtained by only removing cuts of size at most \(\delta =O(c\operatorname{polylog}{n})\)  from \(G\) .
In the following three subsections, we describe the ideas behind this new certificate, the technical challenges encountered in efficiently maintaining it, and why such a certificate is relevant for decremental connectivity algorithms.
