قَضیّهٔ چهاررَنگ یا حدس چهاررنگ از مسائل مشهور و قدیمی ریاضیات است که سال ها اثبات نشده مانده بود. به بیان ساده (و نادقیق) این قضیه می گوید:
مجموعی اجتناب ناپذیر دربر دارندهٔ نواحی ای می باشد که هر نقشه حداقل باید یکی از آن ها را دارا باشد.
یک آرایش کاهش پذیر وضعیتی از کشورهاست که نمی توانند در یک مثال نقض کمینه اتفاق بیفتند. اگر در یک نقشه یک آرایش کاهش پذیر وجود داشته باشد، نقشه می تواند به یک نقشه کوچکتر کاهش یابد. حال اگر این نقشه کوچکتر بتواند با چهار رنگ رنگ آمیزی شود، نقشه اصلی هم می تواند با چهار رنگ رنگ آمیزی شود. این به این معنی است که اگر نقشه اصلی نتواند با چهار رنگ رنگ شود نقشه کوچکتر هم نمی تواند، پس نقشه اصلی کمینه نیست.
سه رنگ برای نقشه های ساده تر کافیست ولی یک رنگ چهارم اضافی برای برخی نقشه ها لازم است. مثل نقشه هایی که در آن ها یک ناحیه با تعداد فرد نواحی دیگر احاطه شده است که به یکدیگر در یک دایره وصل هستند. قضیه ۵ رنگ که اثباتی کوتاه و ابتدایی دارد، بیان می کند که ۵ رنگ برای رنگ آمیزی نقشه کافیست . این قضیه در اواخر قرن ۱۹ اثبات شده است(هیووو ۱۸۹۰). اثبات اینکه ۴ رنگ کافیست بسیار سخت تر است. تعدادی اثبات های غلط و مثال های نقض از زمان ارائه قضیه ۴ رنگ در ۱۸۵۲ بیان شده اند.
این مسئله به صورت معادله ابتدا درسال۱۸۵۲ عنوان شد و سرانجام در سال ۱۹۷۶ با کمک رایانه توسط کی اپپل و و. هیکن حل شد. این اولین قضیه مهمی بود که با استفاده از کامپیوتر به اثبات رسید. آن ها نشان دادند که مجموعه ای از ۱۹۳۶ نقشه وجود دارد که هیچ کدام از آن ها نمی توانند قسمتی از یکی از کوچکترین مثال نقض های قضیه چهار رنگ باشند. اپل و هیکن از یک برنامه کامپیوتری خاص منظوره استفاده کردند تا ثابت کنند هیچ کدام از این نقشه ها از این قاعده مستثنا نیستند. علاوه بر این هر نقشه ای فارغ از این که مثال نقض هست یا نه، حتماً قسمتی را شامل می شود که شبیه یکی از آن ۱۹۳۶ نقشه می باشد و اثبات این نیاز به صدها صفحه تحلیل دست نویس بود. اپل و هیکن نتیجه گرفتند که اگر بخواهد کوچکترین مثال نقضی وجود داشته باشد باید شامل یکی از آن ۱۹۳۶ نقشه باشد. این تناقض به این معنی بود که هیچ مثال نقضی وجود ندارد و قضیه درست می باشد. در ابتدا اثبات آن ها از طرف همه ریاضیدان ها مورد تأیید واقع نشد، چرا که چک کردن یک اثبات کامپیوتری توسط انسان امکان پذیر نبود(Swart ۱۹۸۰).
بیان شهودی قضیه چهار رنگ، یعنی:"در هر افرازی از یک صفحه، که نقشه نامیده می شود، هر ناحیه می تواند به طوری رنگ شود که هیج دو ناحیه مجاوری هم رنگ نباشند و در این رنگ آمیزی از بیشتر از چهار رنگ استفاده نشود"، نیازمند تفسیر و درک مناسب و درستی است. برای مثال هر ناحیه نقشه باید پیوسته باشد. در دنیای واقعی، همه کشورها پیوسته نیستند(برای مثال ایالت آلاسکا در آمریکا و نخجوان در آذربایجان). به علت یکپارچه نبودن قلمرو بعضی کشورها ممکن است چهار رنگ کافی نباشد.
مجموعی اجتناب ناپذیر دربر دارندهٔ نواحی ای می باشد که هر نقشه حداقل باید یکی از آن ها را دارا باشد.
یک آرایش کاهش پذیر وضعیتی از کشورهاست که نمی توانند در یک مثال نقض کمینه اتفاق بیفتند. اگر در یک نقشه یک آرایش کاهش پذیر وجود داشته باشد، نقشه می تواند به یک نقشه کوچکتر کاهش یابد. حال اگر این نقشه کوچکتر بتواند با چهار رنگ رنگ آمیزی شود، نقشه اصلی هم می تواند با چهار رنگ رنگ آمیزی شود. این به این معنی است که اگر نقشه اصلی نتواند با چهار رنگ رنگ شود نقشه کوچکتر هم نمی تواند، پس نقشه اصلی کمینه نیست.
سه رنگ برای نقشه های ساده تر کافیست ولی یک رنگ چهارم اضافی برای برخی نقشه ها لازم است. مثل نقشه هایی که در آن ها یک ناحیه با تعداد فرد نواحی دیگر احاطه شده است که به یکدیگر در یک دایره وصل هستند. قضیه ۵ رنگ که اثباتی کوتاه و ابتدایی دارد، بیان می کند که ۵ رنگ برای رنگ آمیزی نقشه کافیست . این قضیه در اواخر قرن ۱۹ اثبات شده است(هیووو ۱۸۹۰). اثبات اینکه ۴ رنگ کافیست بسیار سخت تر است. تعدادی اثبات های غلط و مثال های نقض از زمان ارائه قضیه ۴ رنگ در ۱۸۵۲ بیان شده اند.
این مسئله به صورت معادله ابتدا درسال۱۸۵۲ عنوان شد و سرانجام در سال ۱۹۷۶ با کمک رایانه توسط کی اپپل و و. هیکن حل شد. این اولین قضیه مهمی بود که با استفاده از کامپیوتر به اثبات رسید. آن ها نشان دادند که مجموعه ای از ۱۹۳۶ نقشه وجود دارد که هیچ کدام از آن ها نمی توانند قسمتی از یکی از کوچکترین مثال نقض های قضیه چهار رنگ باشند. اپل و هیکن از یک برنامه کامپیوتری خاص منظوره استفاده کردند تا ثابت کنند هیچ کدام از این نقشه ها از این قاعده مستثنا نیستند. علاوه بر این هر نقشه ای فارغ از این که مثال نقض هست یا نه، حتماً قسمتی را شامل می شود که شبیه یکی از آن ۱۹۳۶ نقشه می باشد و اثبات این نیاز به صدها صفحه تحلیل دست نویس بود. اپل و هیکن نتیجه گرفتند که اگر بخواهد کوچکترین مثال نقضی وجود داشته باشد باید شامل یکی از آن ۱۹۳۶ نقشه باشد. این تناقض به این معنی بود که هیچ مثال نقضی وجود ندارد و قضیه درست می باشد. در ابتدا اثبات آن ها از طرف همه ریاضیدان ها مورد تأیید واقع نشد، چرا که چک کردن یک اثبات کامپیوتری توسط انسان امکان پذیر نبود(Swart ۱۹۸۰).
بیان شهودی قضیه چهار رنگ، یعنی:"در هر افرازی از یک صفحه، که نقشه نامیده می شود، هر ناحیه می تواند به طوری رنگ شود که هیج دو ناحیه مجاوری هم رنگ نباشند و در این رنگ آمیزی از بیشتر از چهار رنگ استفاده نشود"، نیازمند تفسیر و درک مناسب و درستی است. برای مثال هر ناحیه نقشه باید پیوسته باشد. در دنیای واقعی، همه کشورها پیوسته نیستند(برای مثال ایالت آلاسکا در آمریکا و نخجوان در آذربایجان). به علت یکپارچه نبودن قلمرو بعضی کشورها ممکن است چهار رنگ کافی نباشد.
wiki: قضیه چهاررنگ