جواب این بخش ⌊𝑛/۲⌋ است. برای هر 𝑛 ، گرافی را در نظر بگیرید که یالهای آن از اجتماع یالهای یک دور همیلتونی و یک ستاره (درختی که تمام یالهای آن در یک رأس مشترک هستند) به وجود آمده است. حال ستاره این گراف را به عنوان درخت 𝑇 در نظر می گیریم. این درخت 𝑛 − ۱ برگ دارد و هر یال حداکثر دو برگ را از درجه یک بودن خارج میکند. پس حداقل ⌈𝑛−۱ / ۲ ⌉ یال نیاز داریم که برابر با ⌊𝑛/۲⌋ میشود.

حال میخواهیم ثابت کنیم همواره با اضافه کردن ⌊𝑛/۲⌋ یال میتوان راس های هر گراف دارای شرایط مسئله را به درجه حداقل دو تبدیل کرد. برای این کار، دور همیلتونی گراف را در نظر میگیریم و یالهای آن را یک در میان انتخاب میکنیم. اگر تعداد رأس های گراف فرد باشد، یک رأس به هیچ یال انتخابی متصل نخواهد بود. یالها را به صورتی انتخاب میکنیم که آن رأس برگ نباشد (هر درخت با 𝑛≥3 رأس حداقل یک رأس با درجه بزر گتر از یک دارد.) توجه کنید که الان ⌊𝑛/۲⌋ یال انتخاب کرده ایم. اگر بتوانیم این یال ها را به درخت اضافه کنیم، درجه تمام رأس ها (به غیر از حداکثر یک رأس غیر برگ) یکی افزایش می یابد و هیچ رأس درجه یکی باقی نمی ماند. اما ممکن است بعضی از یالهای انتخابی جزو یالهای درخت باشند و نتوان آنها را اضافه کرد. در این صورت، به ازای هر یال انتخابی که عضو درخت است، با توجه به این که یک سر این یال برگ است و سر دیگر آن برگ نیست، بجای آن یک یال دیگر متصل به آن برگ را انتخاب میکنیم (با توجه به برگ بودن این رأس، یال انتخابی جدید قطعاً درون درخت نیست.) با اینکار تعداد یالهای انتخابی تغییری نمی کند و تمام برگ ها حداقل به یک یال انتخابی متصل خواهند بود. پس با انتخاب این یالها که حداکثر ⌊𝑛/۲⌋ تا هستند، درجه همه رأس ها حداقل ۲ خواهد بود.