====== سوال ۱۰ ======
{{:سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۹:109.png |}}
تعدادی نقطه و پاره‌خط مانند شکل مقابل موجود است. رنگ‌آمیزی نقاط را بدین ترتیب تعریف می‌کنیم: به هر نقطه یک رنگ نسبت می‌دهیم٬ به طوری که دو نقطه که با یک پاره‌خط به هم وصل شده‌اند٬ هم‌رنگ نباشند. گزینه‌ی صحیح را انتخاب کنید.


  - می‌توان نقاط را با ۳ رنگ٬ رنگ‌آمیزی کرد
  - می‌توان نقاط را با ۴ رنگ٬ رنگ‌آمیزی کرد
  - با حذف هر پاره‌خط٬ نقاط را می‌توان با ۳ رنگ٬ رنگ‌آمیزی کرد
  - گزینه‌های ۱ و ۲ و ۳
  - گزینه‌های 2 و ۳

<پاسخ>
گزینه (5) درست است.

{{:سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۹:10.png |}}

سه راس $d  ، a$ و $e$  سه رنگ متمایز دارند و نیز سه راس $d  ، g$ و $e$  نیز سه رنگ متمایز دارند٬ بنابراین اگر بخواهیم رئوس را فقط با سه رنگ٬ رنگ‌آمیزی کنیم آن‌گاه $a$ و $g$   هم‌رنگ خواهند بود. به همین ترتیب معلوم می‌شود که $a$  و $f$ هم‌رنگ هستند که در این صورت دو راس $f$  و $g$  که به هم وصل هستند هم‌رنگ شده و با فرض داده شده تناقض ایجاد می‌کند.

شکل داده شده را با ۴ نوع رنگ به شکل زیر می‌توان رنگ کرد:

$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$ آبی:$b,e$  $\quad\quad\quad\quad\quad\quad$ سبز: $a,g$


$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$ زرد:$f$  $\quad\quad\quad\quad\quad\quad$ قرمز: $d,c$

و همچنین قابل بررسی است که با حذف هر یال رنگ‌آمیزی شکل با سه رنگ امکان‌پذیر است.



</پاسخ>
  * [[سوال ۱۱|سوال بعد]]
  * [[سوال ۹|سوال قبل]]