گراف ‎$G$‎ داده شده است. افراز رئوس ‎$G$‎ به ‎$k$‎ زیرمجموعه‌ی ‎$S_1$‎، ‎$S_2$‎، ‎$\cdots$‎، ‎$S_k$‎ را محکم می‌نامیم اگر برای هر ‎$1 \leq i \leq k$‎ زیرگراف القایی حاصل از رئوس مجموعه‌ی ‎$S_i$‎ دوهمبند یالی باشد (یال برشی نداشته باشد). عدد افراز گراف ‎$G$‎، کمترین مقدار ‎$k$‎ است که به ازای آن برای ‎$G$‎ دست‌کم یک افراز محکم وجود دارد. ثابت کنید اگر عدد افراز ‎$G$‎ برابر ‎$k$‎ باشد، آنگاه تعداد یال‌های ‎$G$‎ حداکثر ‎$C(n-k+1,2)+k-1$‎ است.

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