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

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

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

1 پاسخ

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

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

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