در سؤال قبل فرض کنید یک گراف ۱۶ رأسی داریم که هر رأس آن متناظر با یک رشتهی دودویی ۴ رقمی متمایز است. دو رأس در این گراف به هم یال دارند، اگر و تنها اگر رشتههای متناظر آن رأسها دقیقاً در یک رقم تفاوت داشته باشند. حداقل چند یال به این گراف اضافه کنیم تا فرد زده شود؟
پاسخ
گزینه (۴) درست است.
هر یال اضافه میتواند دو مثلث ایجاد کند و در نتیجه چهار راس را شامل شود. پس حداقل چهار یال لازم است.
از طرفی با اضافه کردن این چهار یال بین $xx00$ و $xx11$ ها گراف فرد زده میشود.