کشوری که گاوی و ببعی در آن زندگی می‌کنند، دارای n شهر می‌باشد (n>۲). بین برخی از شهرهای کشور، جاده‌ی دوطرفه کشیده شده است. هم‌چنین می‌دانیم بین هیچ دو شهری بیش از یک جاده وجود ندارد. از آن‌جایی که مردم این کشور صمیمی هستند، می‌دانیم در هر شهری که باشیم، با استفاده از جاده‌های این کشور می‌توانیم به هر شهر دیگر که بخواهیم، برسیم. ارزش یک شهر برابر است با تعداد شهرهایی که به طور مستقیم با یک جاده به آن شهر متصل هستند. ببعی در یکی از شهرهای این کشور قرار دارد. گاوی که در شهر دیگری است، می‌خواهد به دیدن ببعی برود. می‌دانیم اگر گاوی در مسیر رفتن به شهر ببعی، از شهری با ارزش k عبور کند، باید k تومان عوارض بدهد (شهر آغاز و پایان مسیر نیز مشمول عوارض هستند). از آن جایی که گاوی دوست ندارد زیاد پول خرج کند، مسیری را انتخاب می‌کند که کمترین هزینه را داشته باشد.
پاسخ
کشور مورد نظر را به گراف مدل کنید. به جای هر شهر یک راس و به جای هر جاده یک یال در نظر بگیرید. ارزش یک شهر برابر با درجه راس متناظر آن است. هزینه یک مسیر نیز برابر است با مجموع درجات راس‌های داخل مسیر.
الف) یک گراف کامل را در نظر بگیرید. یال بین دو راس $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$ است.