این مسئله را فقط با روش احتمالاتی حل کنید.

یک گراف ساده‌ی ‎$n$‎ رأسی با مجموعه رئوس ‎$V$‎ داریم که در آن درجه‌ی رأس ‎$u$‎ را با ‎$d(u)$‎ نشان می‌دهیم. ثابت کنید می‌توان ‎$\displaystyle\sum_{u\in V}{\frac {1}{d(u)+1}}$‎ تا از رئوس این گراف را انتخاب کرد، به طوری‌که هیچ دو رأس انتخاب شده‌ای به هم وصل نباشند. ‎

راهنمایی: ابتدا رئوس را به صورت تصادفی از ‎۱‎ تا ‎$n$‎ شماره‌گذاری کنید.

• سوال بعد
• سوال قبل