قطر یک گراف بیش‌ترین فاصله بین هر دو راس آن می‌باشد. یک گراف $k$ - بحرانی است اگر قطر آن $k$ بوده و با برداشتن هر یال گراف قطر آن افزایش یابد. ثابت کنید گراف $k$ - بحرانی با $v$ راس و حداقل $2 \lfloor \frac{v}{k+1} \rfloor^2 + \lfloor \frac{v}{k+1} \rfloor (k+v\quad mod \quad (k+1)-2)$ یال وجود دارد. با ارائه مثالی نشان دهید که این مقدار لزوما یک حد بالا نیست.

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