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

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

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

  * [[سوال ۲|سوال قبل]]