سال‌ها پیش فردی به نام پترسن گراف زیر را از صندوق‌چه‌ی سلطان دزدید و به نام خود زد!

سلطان دلش برای این گراف تنگ شده است و می‌خواهد اندکی با آن بازی کند! او در ابتدا رأس‌های گراف را با قرمز و آبی رنگ می‌کند. سپس هر مرحله به طور هم‌زمان رنگ هر رأس را برابر با رنگی قرار می‌دهد که در همسایه‌هایش بیش‌تر تکرار شده است.

سلطان در ابتدا به چند طریق می‌تواند سه رأس را قرمز و بقیه را آبی کند، طوری که هم‌واره حداقل یک رأس قرمز در گراف باقی بماند؟ رأس‌های گراف را متمایز در نظر بگیرید.

1. 5
2. 120
3. 30
4. 20
5. 12

کمینه‌ی $k$ را بیابید، طوری که سلطان در ابتدا به هر روشی که $k$ رأس را قرمز و بقیه را آبی کند، هم‌واره دست کم یک رأس قرمز در گراف باقی بماند.

1. 5
2. 3
3. 4
4. 7
5. 6

• سوال قبل
• سوال بعد