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

پاسخ:

طبق تعریف مکمل، دو رأس متمایز \(v\) و \(u\) در \(\overline{G}\) به هم وصل‌اند اگر و تنها اگر در \(G\) به هم وصل نباشند. پس برای هر رأسِ \(u\) از \(V(G)\) که با \(v\) برابر نیست، دقیقاً یکی از دو حالت زیر رخ می‌دهد:

• \(uv\) یال \(G\) است، و در این صورت \(uv\) یال \(\overline{G}\) نیست.
• \(uv\) یال \(G\) نیست، و در این صورت \(uv\) یال \(\overline{G}\) است.

بنابراین هر یک از \(n-1\) رأسِ دیگر، در مجموع یک بار به درجهٔ \(v\) در \(G\) و یک بار به درجهٔ \(v\) در \(\overline{G}\) کمک می‌کند. یعنی:

\[d_G(v)+d_{\overline{G}}(v)=n-1\]