سوال ۳۱

شهرها را به دسته $A$ و $B$ تقسیم می‌کنیم. $B$ شامل شهرهایی است که بین هیچ دوتایی از آن‌ها جاده مستقیم وجود ندارد و تعداد آن‌ها حداکثر ممکن را دارد معلووماست که تعدد این شهرها برابر با $b$ می‌باشد. اگر بخواهیم تعداد مراکز کنترل ترافیک حداقل باشد کافی است به تمام شهر‌های دسته‌ی $A$ مرکز کنترل ترافیک اختصاص دهیم. ضمنا لازم نیست به هیچ کدام از اعضای مجموعه‌ی $B$ مرکزی اختصاص دهیم زیرا هر کداماز آن‌ها حداقل به یکی از اعضای مجموعه‌ی $A$ مستقیما جاده دارند( چون در غیر این صورت عضوی از $A$ که به هیچ کدام از اعضای $B$ جاده نداشته باشد باید جز مجموعه‌ی $B$ قرار می‌گرفت). پس تعداد اعضای $A$ حداکثر برابر با $a$ می‌باشد. پس ‎$a+b$ از تعداد شهر‌ها بیش‌تر نیست.