گراف بدون جهت $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|})$ است.