گراف $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$ است.