====== سوال ۲ ======



می‌خواهیم رئوس گراف زیر را با قرمز و آبی رنگ کنیم. باید طوری این کار انجام شود که هر رأس (چه قرمز و چه آبی) دست‌کم یک رأس قرمز مجاور داشته باشد. توجه کنید در یک گراف دو رأس را 
**مجاور**
 گوییم، اگر با یک یال به هم وصل باشند. کمینه‌ی تعداد رأس‌های قرمز چیست؟
{{ :سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۲۷:2-1.png?200 |}}
  - ۳
  - ۶
  - ۲
  - ۴
  - ۵
<پاسخ>
 گزینه‌ی ۳ درست است.
با قرمز کردن تنها یک رأس نمی‌توان به هدف رسید، زیرا خود آن رأس، مجاور قرمز نخواهد داشت.

با قرمز کردن دو رأس  به شکل زیر نیز کار انجام می‌شود. 

{{ :سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۲۷:2-2.png?200 |}}
پس پاسخ برابر ۲ است.

</پاسخ>

  * [[سوال ۱|سوال قبل]]
  * [[سوال ۳|سوال بعد]]