درس هفتم: درجه رأس در گراف

رأسی را در گرافی در نظر بگيريد. تعداد يالهايي از آن گراف که اين رأس يک انتهای آنها است را درجه آن رأس می ناميم (طوقه در يک رأس دو عدد به درجه اضافه می کند.) اگر گراف را G  و رأس را v بناميم آنگاه درجه رأس v در گراف G را با  d_G(v) يا با  d(v)  نشان می دهيم.

مسئله : شش نفر به طور اتفاقی در جايی گرد هم می آيند. اگر رابطه آشنايی بين آنها دو طرفه باشد، ثابت کنيد يا سه نفر هستند که دو به دو يکديگر را بشناسند يا سه نفر هستند که دو به دو يکديگر را نشناسند.