به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
+1 امتیاز
243 بازدید
سوال شده در دبیرستان و دانشگاه توسط
ویرایش شده توسط

ثابت کنید در گراف ساده $G$ :

$q \leq \delta +{p-1 \choose{2} }$

که $ \delta $ مینیمم درجه است.

1 پاسخ

+2 امتیاز
پاسخ داده شده توسط

راسی را با کمترین درجه در گراف در نظر می گیریم در بین $p-1 $ راس باقیمانده حداکثر${p-1 \choose{2} }$ یال موجود است و راسی که ما انتخاب کردیم با $ \delta $ یال با این مجموعه $p-1 $ راسی وصل است لذا حداکثر یال در گراف برابر است با:$ \delta +{p-1 \choose{2} }$ پس $$q \leq \delta +{p-1 \choose{2} }$$

به محفل ریاضی ایرانیان خوش آمدید!
کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
حمایت مالی
...