چرا در گراف های با حداقل دو گره، می توان دو گره یافت که درجه شان یکسان باشند؟

Question

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

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

Comments

$p$ در این سوال چیه؟

---

تعداد راس ها

Answer 1

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