کشور مورد نظر را به گراف مدل کنید. به جای هر شهر یک راس و به جای هر جاده یک یال در نظر بگیرید. ارزش یک شهر برابر با درجه راس متناظر آن است. هزینه یک مسیر نیز برابر است با مجموع درجات راس‌های داخل مسیر.

الف) یک گراف کامل را در نظر بگیرید. یال بین دو راس $a$‌ و $b$ را از این گراف جدا کنید. حال ببعی را در راس $a$ و گاوی را در راس $b$ قرار دهید. اکنون هزینه سفر برابر است با:

$$n-2+n-2+n-1=3n-5$$

ب) فرض کنید ببعی در راس $a$ و گاوی در راس $b$ است. کوتاه‌ترین مسیر را از $a$ به $b$ در نظر بگیرید. به جز یال‌های خود مسیر بین هیچ دو راسی داخل مسیر یال نخواهیم داشت چون اگر یال باشد مسیر کوتاه‌تر می‌شود. هر راس خارج ا زمسیر نیز حداکثر سه یال به راس‌های داخل مسیر دارد، چون در غیر این صورت دوباره مسیر کوتاه‌تری می‌توانستیم پیدا کنیم. حال مجموع درجات راس‌های داخل مسیر را می‌شماریم. به ازای هر یال داخل مسیر به مجموع درجات دو واحد اضافه می‌شود. به ازای هر یال از یک راس خارج از مسیر به یک راس داخل مسیر هم یک واحد به مجموع درجات اضافه می‌شود. اگر تعداد راس‌های درون مسیر $k$ باشد، هزینه کل ما حداکثر برابر با: $2\times (k-1)+3\times (n-k)=3n-k-2$

اگر $k>2$ باشد که سوال حل است. در غیر این صورت مسیر ما فقط متشکل از دو راس بوده است که هر کدام حداکثر می‌توانستند درجه‌ای حداکثر برابر با $n-1$ داشته باشند. پس در آن صورت هزینه کل ما برابر با $2n-2$ می‌شد که با توجه به این‌که $n>2$ است، $2n-2\geq 3n-5$ است.