قضیه پنج رنگ نتیجه ای است از نظریه گراف که صفحه ای به چند منطقه تقسیم شده داده می شود. مناطق به گونه ای به پنج رنگ مختلف رنگ آمیزی می شوند که هیچ دو منطقه مجاوری رنگ یکسان نداشته باشند.قضیه پنج رنگ از قضیه چهار رنگ می رسد اما به طور قابل توجهی اثباتش از آن ساده تر است. اثبات این قضیه بر مبنای تلاش شکست خورده ای برای اثبات قضیه چهار رنگ توسط آلفرد کمپ در سال ۱۸۷۹ می باشد. یازده سال بعد پرسی جان هیوود یک خطا از آن پیدا کرد و بر مبنای کار کمپ قضیه پنج رنگ را اثبات نمود.
S4: همه رئوس باقی مانده با درجه حداکثر چهار یا درجه پنج و حداکثر چهار رأس مجاور مجزا (بسته به یال ها چندگانه) را در بردارد.
S5: همه رئوس باقی مانده که درجه پنج، پنج رأس مجاور مجزا و حداقل یک رأس مجاور با درجه حداکثر شش دارند را در بر می گیرد.
Sd: همه رئوسی که قبلاً از گراف حذف شده اند را به ترتیب حذف شدنشان شامل می شود.
در ابتدا یک گراف مسطح G را به نقشه داده شده نسبت می دهیم به این صورت که هر منطقه را متناظر با یک رأس در نظر می گیریم و بین دو رأس یال وجود دارد اگر و تنها اگر بین دو منطقه متناظر مرز مشترکی باشد؛ بنابراین حالا مسئله به مسئله رنگ آمیزی گراف تبدیل شده است: رنگ کردن رئوس گراف به طوری که هیچ یالی دو سر همرنگ نداشته باشد.اثبات بر مشخصه اویلر استوار است تا نشان دهد حتماً باید یک رأس V وجود داشته باشد که بین حداکثر پنج یال مشترک است و با توجه به این که G مسطح است مثلاً می تواند در یک صفحه بدون یال های متقاطع تعبیه شود.حال V را از G حذف می کنیم. گراف از این کار حاصل می شود که یک رأس کمتر از G دارد. پس ما می توانیم با استقرا فرض کنیم که این را می توان با پنج رنگ، رنگ آمیزی کرد. V حتماً باید به پنج رأس دیگر متصل شود؛ چون در غیر این صورت می تواند در گراف G با رنگی که در آن ها استفاده نشده است، رنگ آمیزی شود. پس حالا به پنج رأس V 1 {\displaystyle V_{1}} ، V 2 {\displaystyle V_{2}} ، V 3 {\displaystyle V_{3}} ، V 4 {\displaystyle V_{4}} ، V 5 {\displaystyle V_{5}} نگاه می کنیم که در ترتیب دایره ای مجاور V هستند (که بستگی به این دارد که چگونه G را نوشته ایم). اگر ما همه پنج رنگ را استفاده نکرده باشیم، مسلماً می توانیم رأس V را به رنگی متفاوت از آن ها رنگ آمیزی کنیم و گرافی پنج رنگ را تحویل دهیم.پس ما می توانیم فرض کنیم که رئوس به ترتیب رنگ های ۱ تا ۵ را گرفته اند.حال زیر گراف G 13 {\displaystyle G_{13}} از G ′ {\displaystyle G'} را در نظر می گیریم که تنها از رئوسی تشکیل شده که رنگ های ۱ و ۳ را دارند و یال هایی که دو تا از این رئوس را به هم متصل می کند. اگر V 1 {\displaystyle V_{1}} و V 3 {\displaystyle V_{3}} در مؤلفه های همبندی متفاوتی از G 13 {\displaystyle G_{13}} باشند، می توانیم رنگ آمیزی مؤلفه همبندی شامل V 1 {\displaystyle V_{1}} را معکوس کنیم که بنابراین رأس V رنگ ۱ را می گیرد و کار تمام است.اما اگر V 1 {\displaystyle V_{1}} و V 3 {\displaystyle V_{3}} در مؤلفه های همبندی یکسانی از G 13 {\displaystyle G_{13}} بودند، می توانیم مسیری در G 13 {\displaystyle G_{13}} که آن دو را به هم متصل می نماید پیدا نماییم که ترتیبی از یال ها و رئوس فقط رنگ شده با ۱ و ۳ باشد.حال زیر گراف G 24 {\displaystyle G_{24}} از G ′ {\displaystyle G'} را که در بر گیرنده رئوس رنگ شده با ۲ و ۴ و یال های متصل کننده این رئوس به هم است را در نظر می گیریم و روندی مشابه قبلی برای آن اجرا می کنیم. پس یا می توانیم رنگ آمیزی زیر گراف G 24 {\displaystyle G_{24}} را برعکس نموده و رأس V را به رنگ ۲ بزنیم یا از مسیری متشکل از رئوس تنها رنگ شده با ۲ و ۴، V 2 {\displaystyle V_{2}} و V 4 {\displaystyle V_{4}} را به هم متصل نماییم. احتمال بعدی به روشنی نامعقول است که مسیری با مسیر ساخته شده در G 13 {\displaystyle G_{13}} تقاطع داشته باشد؛ بنابراین مخالف با استنباط اولیه G در واقع می تواند با پنج رنگ، رنگ آمیزی شود.
در سال ۱۹۹۶، رابرتسون، ساندرز، سیمور و توماس یک الگوریتم چهار رنگ کردن از درجه دوم در «گراف مسطح کارآمد چهار رنگ کردن» خود تعریف کردند. در همان جا، آن ها مختصراً یک الگوریتم پنج رنگ کردن در زمان خطی تعریف کردند که به طور مجانبی بهینه بود. الگوریتمی که در این جا توصیف شده بر روی چند گراف عمل می کند و بر قابلیت داشتن چندین نسخه از یال ها بین یک جفت رأس تکیه دارد. این قضیه بر اساس قضیه ورنیک می باشد که در پایین آمده است:
قضیه ورنیک: فرض می کنیم G یک گراف مسطح غیر خالی است که هیچ منطقه ای ندارد که با دو یال محدود شده باشد و حداقل درجه پنج دارد. پس G حتماً یک رأس از درجه پنج دارد که مجاور رأسی با درجه حداکثر شش است.
S4: همه رئوس باقی مانده با درجه حداکثر چهار یا درجه پنج و حداکثر چهار رأس مجاور مجزا (بسته به یال ها چندگانه) را در بردارد.
S5: همه رئوس باقی مانده که درجه پنج، پنج رأس مجاور مجزا و حداقل یک رأس مجاور با درجه حداکثر شش دارند را در بر می گیرد.
Sd: همه رئوسی که قبلاً از گراف حذف شده اند را به ترتیب حذف شدنشان شامل می شود.
در ابتدا یک گراف مسطح G را به نقشه داده شده نسبت می دهیم به این صورت که هر منطقه را متناظر با یک رأس در نظر می گیریم و بین دو رأس یال وجود دارد اگر و تنها اگر بین دو منطقه متناظر مرز مشترکی باشد؛ بنابراین حالا مسئله به مسئله رنگ آمیزی گراف تبدیل شده است: رنگ کردن رئوس گراف به طوری که هیچ یالی دو سر همرنگ نداشته باشد.اثبات بر مشخصه اویلر استوار است تا نشان دهد حتماً باید یک رأس V وجود داشته باشد که بین حداکثر پنج یال مشترک است و با توجه به این که G مسطح است مثلاً می تواند در یک صفحه بدون یال های متقاطع تعبیه شود.حال V را از G حذف می کنیم. گراف از این کار حاصل می شود که یک رأس کمتر از G دارد. پس ما می توانیم با استقرا فرض کنیم که این را می توان با پنج رنگ، رنگ آمیزی کرد. V حتماً باید به پنج رأس دیگر متصل شود؛ چون در غیر این صورت می تواند در گراف G با رنگی که در آن ها استفاده نشده است، رنگ آمیزی شود. پس حالا به پنج رأس V 1 {\displaystyle V_{1}} ، V 2 {\displaystyle V_{2}} ، V 3 {\displaystyle V_{3}} ، V 4 {\displaystyle V_{4}} ، V 5 {\displaystyle V_{5}} نگاه می کنیم که در ترتیب دایره ای مجاور V هستند (که بستگی به این دارد که چگونه G را نوشته ایم). اگر ما همه پنج رنگ را استفاده نکرده باشیم، مسلماً می توانیم رأس V را به رنگی متفاوت از آن ها رنگ آمیزی کنیم و گرافی پنج رنگ را تحویل دهیم.پس ما می توانیم فرض کنیم که رئوس به ترتیب رنگ های ۱ تا ۵ را گرفته اند.حال زیر گراف G 13 {\displaystyle G_{13}} از G ′ {\displaystyle G'} را در نظر می گیریم که تنها از رئوسی تشکیل شده که رنگ های ۱ و ۳ را دارند و یال هایی که دو تا از این رئوس را به هم متصل می کند. اگر V 1 {\displaystyle V_{1}} و V 3 {\displaystyle V_{3}} در مؤلفه های همبندی متفاوتی از G 13 {\displaystyle G_{13}} باشند، می توانیم رنگ آمیزی مؤلفه همبندی شامل V 1 {\displaystyle V_{1}} را معکوس کنیم که بنابراین رأس V رنگ ۱ را می گیرد و کار تمام است.اما اگر V 1 {\displaystyle V_{1}} و V 3 {\displaystyle V_{3}} در مؤلفه های همبندی یکسانی از G 13 {\displaystyle G_{13}} بودند، می توانیم مسیری در G 13 {\displaystyle G_{13}} که آن دو را به هم متصل می نماید پیدا نماییم که ترتیبی از یال ها و رئوس فقط رنگ شده با ۱ و ۳ باشد.حال زیر گراف G 24 {\displaystyle G_{24}} از G ′ {\displaystyle G'} را که در بر گیرنده رئوس رنگ شده با ۲ و ۴ و یال های متصل کننده این رئوس به هم است را در نظر می گیریم و روندی مشابه قبلی برای آن اجرا می کنیم. پس یا می توانیم رنگ آمیزی زیر گراف G 24 {\displaystyle G_{24}} را برعکس نموده و رأس V را به رنگ ۲ بزنیم یا از مسیری متشکل از رئوس تنها رنگ شده با ۲ و ۴، V 2 {\displaystyle V_{2}} و V 4 {\displaystyle V_{4}} را به هم متصل نماییم. احتمال بعدی به روشنی نامعقول است که مسیری با مسیر ساخته شده در G 13 {\displaystyle G_{13}} تقاطع داشته باشد؛ بنابراین مخالف با استنباط اولیه G در واقع می تواند با پنج رنگ، رنگ آمیزی شود.
در سال ۱۹۹۶، رابرتسون، ساندرز، سیمور و توماس یک الگوریتم چهار رنگ کردن از درجه دوم در «گراف مسطح کارآمد چهار رنگ کردن» خود تعریف کردند. در همان جا، آن ها مختصراً یک الگوریتم پنج رنگ کردن در زمان خطی تعریف کردند که به طور مجانبی بهینه بود. الگوریتمی که در این جا توصیف شده بر روی چند گراف عمل می کند و بر قابلیت داشتن چندین نسخه از یال ها بین یک جفت رأس تکیه دارد. این قضیه بر اساس قضیه ورنیک می باشد که در پایین آمده است:
قضیه ورنیک: فرض می کنیم G یک گراف مسطح غیر خالی است که هیچ منطقه ای ندارد که با دو یال محدود شده باشد و حداقل درجه پنج دارد. پس G حتماً یک رأس از درجه پنج دارد که مجاور رأسی با درجه حداکثر شش است.
wiki: قضیه پنج رنگ