گزینه‌ی ۳ درست است.

رأس‌های اطراف گراف را به ترتیب از $v_1$ تا $v_6$ نام‌گذاری می‌کنیم. رأس $v_1$ را در نظر می‌گیریم. در صورتی که همزمان یال‌های آن با رأس‌های $\langle v_3, v_4 \rangle$ و یا $\langle v_5, v_6 \rangle$ اضافه شود، زیرگراف کامل ۴ رأسی تشکیل می‌شود. در نتیجه حداکثر می‌توان ۲ یال از رأس $v_1$ اضافه کرد. همین استدلال را می‌توان برای رأس‌های $v_2$ تا $v_6$ نیز ارائه داد. در نتیجه حداکثر ۶ یال می‌توان به گراف اضافه نمود:

گزینه‌ی ۵ درست است.

یک گراف $n$ رأسی در صورتی که بیش از $\bigl\lfloor \frac{n^2}{4} \bigr\rfloor$ یال داشته باشد، شامل دور به طول ۳ خواهد بود و همچنین گراف $Q_n$ شامل $2^{n-1} \times n$ یال است. در نتیجه حداکثر تعداد یال‌هایی که می‌توان به گراف اضافه کرد برابر است با: $$\frac{2^16}{4} - 2^7 \times 8 = 15360$$ برای رسیدن به این بیشینه نیز کافی است رأس‌هایی که رشته‌ی متناظر با آن‌ها شامل تعداد زوجی رقم ۱ می‌باشند را در یک بخش و سایر رأس‌ها را در بخش دیگر قرار می‌دهیم. گراف حاصل دوبخشی است و می‌توانیم تمام یال‌هایی که بین دو بخش گراف وجود ندارند را اضافه کنیم.