Пусть минимальный разрез состоит из ребер. Тогда все вершины имеют степень не меньше (Если бы какая-нибудь вершина имела степень меньше , то разрез состоял бы менее чем из ребер, противоречие). Поскольку каждое ребро учитывается при подсчете степеней обоих вершин, а суммарная степень вершин не меньше , то граф должен содержать хотя бы ребер. Событие : "стянутое на итерации ребро не входит в минимальный разрез ". Требуется оценить вероятность успеха .

Заметим, что . Оценим вероятности всех сомножителей и подставим значения.

Рассмотрим первую итерацию. По крайней мере из ребер входят в минимальный разрез .

Вероятность ошибки на первой итерации не превосходит . Следовательно для успеха на первой итерации справедлива оценка:

.


В результате стягивания ребра на первой итерации число вершин уменьшилось на одну, тем не менее, осталось хотя бы ребер. На второй итерации получаем:


.


Для остальных вершин вероятности успеха:

.


В результате, когда алгоритм завершит работу, вероятность нахождения минимального разреза составит: