این کشور رو یک گراف در نظر میگیریم. حتما یک راس غیر برشی داره که با حذفش گراف همبند میمونه ( اثبات به کمک مسیر ماکسیمال ). این راس رو راس شروع در نظر میگیریم و به یکی از همسایه های دلخواهش میریم و اون راس رو از گراف حذف میکنیم. (یک مرحله). سپس از اون همسایه تو گراف باقی مونده DFS میزنیم و فقط یال های درخت DFS رو در نظر میگیریم و راس های گراف رو به ترتیب طی شدن در درخت DFS میبینیم. هر یال در این درخت حداکثر دو بار مشاهده شده ( یکبار به سمت پایین و یکبار به سمت بالا برای برگشتن به پدرش) به جز یال راس آخری که مشاهده میشه به پدرش که تنها یکبار مشاهده میشه (بعد از دیدن آخرین راس تمامی مراحل تموم شده و دیگه یال به پدرش رو دوباره طی نمیکنیم!). در مجموع تعداد حرکات میشه : 1+1-(2(n-2)) که در مجموع میشه 2n-4 حرکت.

چون این گراف همبند هست (از هر راس به هر راس دیگه ای میشه رسید) پس حتما یک «زیردرخت فراگیر» داره:‌ زیر مجموعه ای از یالهای درخت به نحوی که بشه از طریق اونها هم از هر راس به هر راس دیگه ای رسید ولی دور نداشته باشه. این زیردرخت فراگیر رو در نظر میگیریم و فکر میکنیم بقیه یالهای گراف وجود ندارن.

هر درخت $n$ راسی $n-1$ یال داره. کافیه یک راس از زیردرخت فراگیر به عنوان «ریشه» رو در نظر بگیریم و از اون پیمایش راسها رو شروع کنیم: در هر مرحله از راسی که در اون هستیم به یک راس میریم که قبلا پیمایش نشده باشه. اگر همه راسهای مجاور راسی که در اون هستیم قبلا پیمایش شده بودند، از همون یالی که اولین بار ما رو به این راس رسونده بود بر میگردیم (به این الگوریتم ساده DFS یا جستجوی عمق اول گفته میشه). به این ترتیب هر یالی دقیقا دو بار پیمایش میشه و همه راسها رو میبینیم: $2\times(n-1)=2n-2$ حرکت.

اما چطور به $2n-4$ برسیم؟ کافیه دقت کنیم وقتی آخرین راس رو پیمایش کردیم دیگه نیازی نیست برگردیم. انتظار داریم با این ترتیب ۲ حرکت صرفه جویی بشه: نپیمودن دوباره یالی که ما رو به آخرین راس رسوند، و نپیمودن دوباره آخرین یالی که متصل به ریشه بود و ازش خارج شدیم (چون دوباره به ریشه بر نمیگردیم). اما ممکنه این دو یال یکی باشند: یعنی آخرین راس مستقیما به ریشه وصل باشه.

برای این که این اتفاق نیافته کافیه ریشه رو یکی از برگهای درخت فراگیر در نظر بگیریم (برگ یعنی راسی از درخت که تنها یک یال بهش متصل هست،‌ یا به عبارت دیگه درجه اش ۱ هست). به این ترتیب اگر یالی که ما رو به راس آخر وصل میکنه همون یالی باشه که ما رو به ریشه وصل میکنه یعنی کلا درخت ما دو راس بیشتر نداره (ریشه و راس آخر) که با $n>2$ متناقض هست.