به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+2 امتیاز
102 بازدید
در دبیرستان و دانشگاه توسط OXIDE (653 امتیاز)
ویرایش شده توسط AmirHosein

ثابت کنید در هر گراف سادهٔ $G=(V,E)$ که دارای $p\geq 2$ گره‌است، حداقل دو گرهٔ هم‌درجه وجود دارد.

منظور از $p$ تعداد گره‌های گراف است یعنی $p=n(V)$ که $n(V)$ یعنی تعداد اعضای مجموعهٔ $V$.

توسط erfanm (12,604 امتیاز)
+1
$p$ در این سوال چیه؟
توسط OXIDE (653 امتیاز)
+1
تعداد راس ها

1 پاسخ

+4 امتیاز
توسط erfanm (12,604 امتیاز)
انتخاب شده توسط OXIDE
 
بهترین پاسخ

از برهان خلف حکم را ثابت میکنیم میدانیم در گرافی با $p $ راس حداکثر درجه برابر است با $p-1 $(زمانی اتفاق می افتد که یک راس با تمام رئوس دیگر مجاور باشد) و اگر فرض کنیم هر راس دارای درجه متفاوتی باشد لذا درجه رئوس اعداد $0,1,2,...,p-1 $ می شوند اما وجود درجه صفر یعنی یکی از راسها با هیچ راس دیگری مجاور نیست و لی این با وجود داشتن راسی از درجه $p-1 $ در تناقض است.


حمایت مالی

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