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

حل:

روستاها را با رأس‌های \(K\)، \(A\) و \(H\) نشان می‌دهیم. هر گرافی که در آن رأسی تنها نباشد، یعنی حداقل یک یال به هر رأس داشته باشد، برای طراحی موردنظر است.

• شکل الف: \(K\) و \(H\) به هم وصل‌اند و \(A\) هم به \(H\) وصل است. هیچ رأسی تنها نیست. این گراف موردنظر است.
• شکل ب: فقط \(K\) و \(A\) به هم وصل‌اند و \(H\) تنها مانده است. این گراف را نباید شمرد.
• شکل پ: هر سه رأس به هم وصل‌اند و مثلث ساخته‌اند. این گراف موردنظر است.
• شکل ت: فقط \(K\) و \(H\) به هم وصل‌اند و \(A\) تنها مانده است. این گراف را نباید شمرد.

پس گراف‌های الف و پ موردنظرند و گراف‌های ب و ت نباید شمرده شوند.