الگوریتم تصادفی زیر روی یک گراف ساده انجام می‌شود:

در هر مرحله، اگر گراف‌مان تک‌راسی بود الگوریتم به پایان می‌رسد. وگرنه دو راس تصادفی از گراف انتخاب می‌شوند؛ اگر به هم متصل بودند یال بین‌شان منقبض می‌شود و این دو راس یکی می‌شوند، اگر متصل نبودند کاری انجام نمی‌دهیم.

برای هر گراف اولیه‌ی $n$-راسی همبند ، با فرض این‌که الگوریتم پایان پذیرفته، ثابت کنید امید ریاضی تعداد مراحل الگوریتم حداکثر $\frac{n(n+1)}4$ می‌باشد.