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

اگر $G$ یک گراف ساده با $p$ گره و $q$ یال و کمینه درجهٔ $\delta$ باشد، آنگاه ثابت کنید که $q\leq\delta+\binom{p-1}{2}$.

+1 امتیاز
2,348 بازدید
در دبیرستان و دانشگاه توسط OXIDE (681 امتیاز)
ویرایش شده توسط AmirHosein

اگر $G$ یک گراف ساده با $p$ گره و $q$ یال و کمینه‌درجهٔ $\delta$ باشد، آنگاه ثابت کنید که $q\leq\delta+\binom{p-1}{2}$.

1 پاسخ

+2 امتیاز
توسط erfanm (13,881 امتیاز)

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

چگونه می توانم به محفل ریاضی کمک کنم؟

کانال تلگرام محفل ریاضی

سوالات مشابه

“ ریاضیدان، کسی است که شباهت ها را بین قضایا دریابد. ریاضیدان بهتر کسی است که بتواند شباهت بین برهان ها را ببیند. بهترین ریاضیدان کسی است که بتواند به شباهت بین نظریه ها توجه کند. و می توان تصور کرد که ریاضیدان نهایی کسی است که بتواند شباهت بین شباهت ها را مشاهده کند.
...