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

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

$p=n(V)$
توسط erfanm
$p$ در این سوال چیه؟
توسط OXIDE
+1
تعداد راس ها

1 پاسخ

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

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

حمایت مالی


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