In this section, we present structural lemmas regarding the \(c\) -edge-connected components, in particular in graphs where a significant fraction of the vertices has degree at least \(\Omega (c)\) . As described in Section REF , at each level of the recursive construction of our \(c\) -certificate, all \(c\) -edge-connected components of the sampled graph are contracted into single vertices in the recursive calls to the next levels. The following structural results show that the number of vertices between subsequent levels shrink by a constant factor, implying a \(O(\log n)\)  bound on the number of levels in our certificate.
We note that some proofs from Sections , REF , and  can be found in Section .
[Benczúr and Karger [1]}]lemmabenczur 
Let \(c\)  and \(n\)  be positive integers. Every graph on \(n\)  vertices with strictly more than \((c-1)(n-1)\)  edges contains a non-trivial \(c\) -edge-connected component.
