جواب مسئله صفحه ۳۸ ریاضیات گسسته

پاسخ:

در گراف کامل \(K_p\) هر رأس با تمام \(p-1\) رأس دیگر مجاور است. پس درجهٔ هر رأس برابر \(p-1\) است:
\[deg(v)=p-1\]

مجموع درجات همهٔ رأس‌ها برابر \(p\) ضرب در \(p-1\) است:
\[\sum deg(v)=p(p-1)\]

هر یال دو سر دارد و در مجموع درجات دو بار شمرده می‌شود. بنابراین تعداد یال‌ها نصف این مجموع است:
\[q(K_p)=\frac{p(p-1)}{2}\]

نتیجه: گراف کامل \(p\) رأسی دارای \(\dfrac{p(p-1)}{2}\) یال است.