====== سوال ۶ ======



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




  - $1$
  - $2$
  - $3$
  - $4$
  - $8$




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

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

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

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