فرض کنید که شهرهای ۱ تا ۷ دور دایرهای به شکل مقابل میباشند. (بین شهرهای مجاور جاده وجود دارد.)
حداکثر چند جادهی دیگر میتوان بین این شهرها کشید به طوری که هیچ دو جادهای همدیگر را قطع نکنند و بین هر دو شهر حداکثر یک جادهی مستقیم وجود داشته باشد. (جادهها هم میتوانند در داخل دایره و هم در خارج آن کشیده شوند.)
پاسخ
گزینه (۳) درست است.
ابتدا با توجه به قضیهی اولر ثابت میکنیم تعداد جادههای مورد نظر نمیتواند بیش از ۸ جاده باشد.
قضیهي اولر به یکی از دو صورت زیر بیان میشود:
هر ناحیه در دور خود حداقل سه یال دارد٬ بنابراین تعداد یالهای موجود در دور تمام نواحی حداقل برابر $3f$ میباشد ولی چون هر یال دقیقا مرز دو ناحیه میباشد٬ با این شمارش هر یک از آنها دو بار شمارش میشوند٬ بنابراین:
$$2e \geq 3f \quad \Rightarrow \quad 2e \geq 3(e+2-7) \quad \Rightarrow \quad e \leq 15$$
چون در شکل داده شده ۷ یال رسم شده پس حداکثر ۸ یال دیگر مطابق شکل زیر میتوان رسم کرد: