تعریف:

• لیست‌های بدون ترتیبعدم یال: اگر بین دو رأس در گراف یالی نباشد.
• گراف مکمل گراف $G$: گرافی با همان رأس‌های گراف $G$ ولی یال‌هایش، عدم یال‌های $G$ است.

گراف معین را گراف $G$ و مکمل گراف معین را $\overline{G}$ می‌نامیم. معین اگر بجای تمامی عدم یال‌های گراف $G$ یک یال اضافه کند، هر رأس از $G$ به تمامی رئوس دیگر یال خواهد داشت. پس درجه هر رأس برابر با $2018 - 1 = 2017$ و فرد خواهد بود. پس این یک روش برای فرد کردن درجه رئوس گراف است و از آنجایی که معین تنها یک روش برای این کار دارد؛ پس تنها روش این است که معین تمامی یال‎های ممکن را بگذارد. گراف یال‌هایی که معین اضافه می‌کند همان گراف عدم یال‌ها یعنی $\overline{G}$ است. حال فرض کنید در $\overline{G}$ یک دور وجود داشته باشد. اگر معین یال‌های این دور را به گراف اضافه نکند باز هم درجه همه رئوس فرد می‌شود زیرا اگر یال‌های یک دور را در نظر بگیریم، هر رأس از گراف یا به $2$ یال متصل است یا به هیچ یالی متصل نیست. پس وجود یا عدم وجود یال‌های یک دور در گراف تغییری در زوجیت درجه رئوس بوجود نمی‌آورد. در نتیجه اگر در $\overline{G}$ یک دور وجود داشته باشد، معین هم می‌تواند یال‌‌های آن دور را به $G$ اضافه کند و هم می‌تواند اضافه نکند و این خود دو روش اضافه کردن یال‌ها است و با توجه به یگانه بودن روش‌ اضافه کردن یال‌ها؛ می‌توان نتیجه گرفت که $\overline{G}$ دور ندارد.

حال اثبات می‌کنیم گرافی که دور ندارد حداکثر $n-1$ یال دارد:

• برهان خلف: فرض کنید گرافی داریم بدون دور که حداقل $n$ یال دارد. حال تعدادی یال از گراف حذف می‌کنیم تا گرافمان دقیقا $n-1$ یال داشته باشد. دقت کنید که با حذف کردن یال‌ها دوری در گراف بوجود نیامده و گراف همچنان بدون دور باقی می‌ماند. حال گرافی بدون دور و $n-1$ داریم. پس یک درخت داریم (درخت). حال اگر یال‌هایی که حذف کردیم را برگردانیم (یعنی به درختمان یکسری یال اضافه کنیم) حتماً گرافی دارای دور بوجود می‌‌آید (ویژگی درخت - ویژگی $6$ام) ولی گراف اولیه ما بدون دور بود، پس به تناقض رسیدیم و فرض خلف غلط است.

پس $\overline{G}$ با توجه به اینکه دور ندارد، حداکثر $n-1$ یال دارد. در نتیجه $G$ حداقل $\binom{2018}{2} - 2018 + 1$ یال دارد. حال برای تکمیل اثبات گرافی $2018$ رأسی می‌سازیم که در آن تنها یک روش برای فرد کردن درجه کل رئوس وجود داشته باشد و نیز دارای $\binom{2018}{2} - 2018 + 1$ یال باشد. گراف را اینگونه درست می‌کنیم: رئوس را از $1$ تا $2018$ شماره گذاری می‌کنیم. رأس $1$ را به رأس دیگری وضل نکرده ولی تمامی رئوس دیگر را به هم وصل می‌کنیم. حال گراف دقیقا $\binom {2017} {2}$ یا همان $\binom{2018}{2} - 2018 + 1$ یال دارد. و تنها روش فرد کردن درجه کل رئوس، وصل کردن رأس $1$ به همه‌ی آنها است. زیرا همه‌ی رئوس $2$ تا $2018$ دارای درجه زوج هستند و تنها روش تغییر درجه هر یک از آنها اضافه کردن یال بین رأس $1$ و رأس مورد نظر است. پس در آخر باید کلیه رئوس به یکدیگر متصل باشند و این تنها روش فرد کردن درجه رئوس است.
گفتیم که تعداد یال‌های گراف $G$ حداقل $\binom{2018}{2} - 2018 + 1$ است و نیز این مقدار با یک مثال قابل دستیابی است. پس جواب $\binom{2018}{2} - 2018 + 1$ یا همان $\binom {2017} {2}$ است.