سوال ۱۰۴ کنکور ارشد ریاضی ۱۴۰۱

به چند طریق می‌توان رأس‌های گراف زیر را با ۳ رنگ قرمز، زرد و آبی رنگ کرد به‌طوری‌که هیچ دو رأس مجاوری هم‌رنگ نباشند؟

(شکل، گرافی ۹ رأسی و متقارن نسبت به محور قائم است. رأس‌ها را چنین نام‌گذاری می‌کنیم: $L$ (چپ‌ترین)، $A$ (بالا سمت چپ)، $B$ (پایین سمت چپ)، $P$ (داخلی چپ)، $M$ (میانی)، $Q$ (داخلی راست)، $C$ (بالا سمت راست)، $D$ (پایین سمت راست)، $R$ (راست‌ترین). یال‌ها عبارت‌اند از:

• بلوک چپ: $L\!-\!A$، $L\!-\!B$، $L\!-\!P$، $A\!-\!P$، $B\!-\!P$؛
• بلوک راست: $R\!-\!C$، $R\!-\!D$، $R\!-\!Q$، $C\!-\!Q$، $D\!-\!Q$؛
• دو یال افقی بلند بالا و پایین: $A\!-\!C$ و $B\!-\!D$؛
• مسیر میانی: $P\!-\!M$ و $M\!-\!Q$ — در مجموع ۱۴ یال.)