درجهی یک رأس در گراف برابر تعداد یالهایی از گراف است که به آن متصل هستند. در گراف مقابل به هر رأس، عددی برابر مجموع درجههای همسایههای آن رأس نسبت میدهیم. فرض کنید مجموع این اعداد برابر A شود. در گام بعدی روی هر یال یک رأس جدید اضافه میکنیم و دوباره برای هر رأس، همان عمل را انجام میدهیم. مجموع اعداد جدید را B مینامیم. B−A چند است؟
پاسخ
گزینه (؟) درست است.
درجهی هر راس از گراف به تعداد درجهی آن راس در نوشتن A به کار میرود بنابراین اگر درجهی رئوس را a2،a1،…،an در نظر بگیریم آنگاه خواهیم داشت:
A=a1×a1+a2×a2+...+an×an=∑ai2
به همین ترتیب معلوم میشود که:
B=∑ai2+(22+22+...+22⏟29تا
⇒B−A=29×4=116
یادآوری میشود که تعداد یالهای گراف داده شده برابر ۲۹ میباشد. همانطور که دیده میشود عدد بهدست آمده در هیچیک از گزینهها نیامده است.