We also need the following lemma due to Abboud et al. [1]}:[Abboud et al. [1]}]
Let \(G = (V, E)\)  be an undirected graph. If \(s\)  is a vertex chosen uniformly at random from \(V\) , then with probability \(\ge 1/2\) , there are \(\ge |V|/4\)  vertices \(t\in V\setminus \lbrace s\rbrace \)  such that the \(t\) -minimal minimum \(s-t\)  cut has \(\le |V|/2\)  vertices on the side of \(t\) .

Here, \(t\) -minimal refers to the minimum \(s-t\)  cut where the side containing \(t\)  is minimized. But, for our purposes, we do not need this qualification since by lem:unique, the minimum \(s-t\)  cut in \(G^{\rm gen}\)  is unique under edge weights \(w^{\prime }\) .
