جواب کار در کلاس صفحه ۴۰ ریاضیات گسسته

الف) گراف \(G\) با \(n\) رأس، \(k\)-منتظم است، یعنی درجهٔ هر رأس آن برابر با \(k\) است. پس مجموع درجات رئوس برابر است با:

\[\sum_{i=1}^{n} \deg(v_i) = \underbrace{k + k + \cdots + k}_{n} = nk\]

طبق قضیه‌ای که در این درس دیدیم، برای هر گراف داریم \(\sum \deg(v_i) = 2q\)، که در آن \(q\) تعداد یال‌هاست. بنابراین:

\[2q(G) = nk\]

\[q(G) = \frac{nk}{2}\]

پس تعداد یال‌های گراف \(G\) برابر \(\dfrac{nk}{2}\) است.

ب) گراف کامل \(K_n\) یک گراف \(n\) رأسی و \((n-1)\)-منتظم است، یعنی هر رأس آن با \(n-1\) رأس دیگر مجاور است. با قرار دادن \(k = n-1\) در قسمت الف داریم:

\[q(K_n) = \frac{n(n-1)}{2}\]

پس تعداد یال‌های گراف کامل \(K_n\) برابر \(\dfrac{n(n-1)}{2}\) است.