We can also apply
the fully dynamic min-cut algorithm of Thorup [1]} which identifies
cuts of size \(n^{o(1)}\)  in \(n^{1/2+o(1)}\)  worst-case time. For \(c=n^{o(1)}\) ,
we then maintain a \(c\) -certificate \(H\)  in \(O(m+n^{3/2+o(1)})\)  total time.
This includes telling which vertices are in the same \(c\) -edge-connected
component. If we further want to answer queries about \(c\) -edge-connectivity between pairs of nodes, we can apply the fully-dynamic data structure of Jin and
Sun [2]} to the \(c\) -certificate \(H\) . By definition,
the answers to these queries are the same in \(H\)  and \(G\) , and the algorithm
takes \(n^{o(1)}\)  time per update or query. Hence the total time for the
updates remains \(O(m+n^{3/2+o(1)})\) , and we can tell
if two vertices are \(c\) -edge-connected in \(n^{o(1)}\)  time.
