المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۴:گراف:سوال ۶

سوال ۶

فرض کنید $G$ یک گراف $r$-منتظم با کمر حداقل $g$ است که کم‌ترین تعداد راس را (بین تمام گراف‌های با این خصوصیات) دارد. نشان دهید که:

  1. قطر $G$ حداکثر $g$ است.
  2. کمر $G$ برابر $g$ است.
  3. $|V(G) \leq \frac{r}{r-2} (r-1)^g$

ابزار صفحه