The uniquely defined \(c\) -edge-connected components of a graph may be found by
repeatedly removing cuts of size at most \(c-1\) . For the reductions, we
need algorithms that can help us in this process. We therefore define the
fully dynamic \(c\) -edge-cut problem as follows. Suppose a graph \(G\)  is subject to edge insertions and/or deletions.
Then, a fully dynamic \(c\) -edge-cut data structure should
maintain any edge \(e\)  that belongs to some cut of size less than \(c\) . A typical application of such a data structure is to repeatedly remove such edges \(e\)  belonging to cuts of size less than \(c\) , which splits \(G\) 
into its \(c\) -edge-connected components.
For each \(c\ge 1\) , denote by \(T_c(n)\)  the amortized time needed by the data structure to find an edge belonging to a cut of size less than \(c\) .
For example, for \(c=1\)  we have \(T_1(n)=O(1)\)  since we do not have to maintain anything. For \(c=2\) , the data structure is required to maintain some bridge
of \(G\)  and it is known that \(T_2(n)=O((\log {n}\cdot \log \log {n})^2)\)  [1]}. For \(c\ge 3\) , in turn, we
have \(T_c(n)=O(n^{1/2}\operatorname{poly}{(c)})\)  [2]}.
