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

الف) هر دانش‌آموز را با یک رأس نشان می‌دهیم و دو رأس را وقتی به هم وصل می‌کنیم که دو دانش‌آموز متناظر با آن‌ها با هم دوست باشند. چون دوستی دوطرفه است، گراف \(G\) ساده است. برای نمونه، گرافی که در شکل می‌بینید یکی از حالت‌های ممکن برای ۷ دانش‌آموز است؛ گراف شما ممکن است با این فرق کند.

ب) طبق قضیه، مجموع درجات رأس‌های هر گراف برابر \(2q\) است و این مجموع همیشه عددی زوج است.
اگر درجهٔ تمام ۷ رأس برابر ۳ باشد، آنگاه:
\[\sum_{i=1}^{7} \deg(v_i) = 3 \times 7 = 21\]
اما ۲۱ عددی فرد است و نمی‌تواند برابر \(2q\) باشد. پس امکان ندارد درجهٔ تمام رئوس این گراف برابر ۳ باشد.

پ) فرض کنیم تعداد افراد جمع فرد باشد، یعنی ۷ نفر، و هر نفر تعداد فردی دوست داشته باشد. در این صورت درجهٔ همهٔ ۷ رأس فرد است، یعنی تعداد رأس‌های فرد گراف برابر ۷ است.
طبق نتیجهٔ درس، تعداد رأس‌های فرد هر گراف عددی زوج است، اما ۷ عددی فرد است. این تناقض نشان می‌دهد که امکان ندارد همهٔ نفرات جمعی با تعداد فرد، دوست فرد داشته باشند.