4색 문제(four color problem)

 

1852년 10월, 영국 런던에 있는 유니버시티 대학(University College)의 대학원생 프렌시스 구드리에(Francis Guthrie)는 영국 지도를 색칠해 나가다가 '인접한 구획들이 같은 색으로 칠해지는 경우가 없게 하려면 최소한 몇 가지의 색이 필요할까?'라는 의문을 갖게 되었다.
결국 영국의 지도에 있는 지역들을 구별하여 색칠하는 데는 4가지 색이면 충분하다는 사실을 알게 되었다. 그는 임의의 구획으로 나누어져 있는 지도를 칠할 때 4가지 색이면 대부분 되는 것 같았지만 확신을 가질 수는 없었다.

다섯 가지 이상의 색을 사용해야 조건에 맞게 그릴 수 있는 지도가 존재할까, 아니면 네 가지 색이면 어떤 지도에서도 인접한 구획들이 다른 색으로 칠해질 수 있음을 증명할 수 있을까?

 

https://m.blog.naver.com/pcswa/224166415839

4색 문제(four color problem)