سوال ۶

در سؤال قبل فرض کنید یک گراف ۱۶ رأسی داریم که هر رأس آن متناظر با یک رشته‌ی دودویی ۴ رقمی متمایز است. دو رأس در این گراف به هم یال دارند، اگر و تنها اگر رشته‌های متناظر آن رأس‌ها دقیقاً در یک رقم تفاوت داشته باشند. حداقل چند یال به این گراف اضافه کنیم تا فرد زده شود؟

  1. $1$
  2. $2$
  3. $3$
  4. $4$
  5. $8$

پاسخ

گزینه (۴) درست است.

هر یال اضافه می‌تواند دو مثلث ایجاد کند و در نتیجه چهار راس را شامل شود. پس حداقل چهار یال لازم است.

از طرفی با اضافه کردن این چهار یال بین $xx00$ و $xx11$ ها گراف فرد‌ زده می‌شود.