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

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

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

• سوال قبل