گراف بدون جهت ‎$G$‎ با ‎$n^2$‎ راس به این صورت ساخته شده است که رئوسش دوتایی‌های ‎$(a,b)$‎ به ازای ‎$1 \leq a‎, ‎b \leq n$‎ می‌باشند. هر راس ‎$(a,b)$‎ به رئوس ‎$(a-1,b)‎, ‎(a+1,b)‎, ‎(a,b-1)‎, ‎(a,b+1)$ (در صورت وجود این رئوس) وصل است. یعنی درجه‌ی هر راس حداکثر ‎۴‎ خواهد شد. مجموعه‌ی ‎$S$‎ از رئوس داده شده است و می‌دانیم ‎$|S| < n^2/2$‎. ثابت کنید تعداد یال‌های بین مجموعه‌ی ‎$S$‎ و بقیه‌ی رئوس گراف ‎$\Omega(\sqrt{|S|})$‎ است.

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