# 4색 정리에 약 30년 만의 새 증명, 지도를 4색으로 칠해 구분하는 알고리즘 대폭 고속화

> https://bookfactory.kr/c/news/11064
> 게시판: 뉴스
> 작성자: tachikoma43
> 작성일: 2026-09-11T06:27:20.605Z

---

어떤 지도든 인접한 지역을 같은 색으로 칠하지 않도록 4가지 색만으로 구분하여 칠할 수 있다는 '4색 정리'에 대해, 일본과 덴마크 등의 연구진으로 구성된 팀이 새로운 증명을 발표했습니다. 이번에도 컴퓨터를 이용한 증명이지만, 기존과 다른 부분에 주목함으로써 다수의 처리를 한데 묶어 수행할 수 있게 되어, 실제로 그래프를 4색으로 구분하여 칠하는 알고리즘도 대폭 고속화되었다고 과학 전문 매체 Quanta Magazine이 해설하고 있습니다.[2603.24880] The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloringhttps://arxiv.org/abs/2603.24880The Four-Color Theorem Gets a Rare New Proof | Quanta Magazinehttps://www.quantamagazine.org/the-four-color-theorem-gets-a-rare-new-proof-20260910/4색 정리의 시작은 1852년까지 거슬러 올라갑니다. 영국의 수학자 프랜시스 가스리가 잉글랜드의 주를 지도상에서 구분하여 칠하던 중, "경계선을 공유하는 지역이 같은 색이 되지 않도록 하려면 어떤 지도든 4가지 색이면 충분하지 않을까"라고 깨달은 것이 계기였습니다. 이 문제는 일견 단순해 보이지만, 모든 지도에 대해 4가지 색으로 충분하다는 것을 수학적으로 증명하는 것은 극히 어려웠습니다. 이 문제를 수학적으로 다루기 위해 지도는 '그래프'라고 불리는 형태로 대체됩니다. 이 그래프는 학교 수학에서 배우는 그래프를 말하는 것이 아니라, 각각의 지역을 점, 즉 '정점'으로 나타내고, 경계선을 공유하는 두 지역에 대응하는 정점을 선, 즉 '간선'으로 연결해 표현한 도형입니다. 그래프를 활용함으로써 4색 문제는 "선으로 연결되어 있는 정점끼리 서로 다른 색으로 하면서, 모든 정점을 4색 이내로 칠할 수 있는가"라는 문제가 됩니다.

byMathPage1879년에는 수학자 알프레드 브레이 켐프가 증명에 성공했다고 발표했습니다. 켐프는 "만약 4색으로는 칠할 수 없는 그래프가 있다면, 그중에서 가장 작은 것을 생각한다"라는 발상을 채택했습니다. 거기서 정점을 1개 제거하면 더 작은 그래프가 되므로 4색으로 칠할 수 있을 것입니다. 이에 남아 있는 그래프의 일부 색을 잘 맞바꾸면, 제거했던 정점을 다시 되돌려 놓아도 4색으로 칠할 수 있음을 보여주려 했습니다. 그러나 1890년, 퍼시 존 히우드에 의해 켐프의 증명에는 오류가 있음이 밝혀졌습니다. 그럼에도 불구하고 2가지 색으로 연결된 정점 집합의 색을 맞바꾸는 '켐프 사슬'이라는 개념 자체는 유용하여, 이후의 올바른 4색 정리 증명으로도 이어졌습니다.

올바른 증명이 등장한 것은 1976년입니다. 케네스 아펠과 볼프강 하켄은 평면 그래프에는 반드시 특정 '배치'가 포함되어 있으며, 이를 이용하면 문제를 더 작은 그래프로 축소할 수 있다는 점을 활용했습니다. 이처럼 그것이 존재하면 사색정리의 최소 반례가 될 수 없음을 보여줄 수 있는 국소적인 구조를 '가약 배치'라고 부릅니다. 간단히 말해, "아무리 거대한 그래프라도 반드시 어딘가에 공략 가능한 작은 패턴이 있다"는 것을 보여주고, 그 패턴을 제거하여 작은 문제를 푼 뒤, 마지막에 원래대로 되돌려놓는 방법입니다. 아펠과 하켄은 조사해야 할 후보를 1482가지까지 줄이고, 각각이 실제로 가약임을 컴퓨터로 확인했습니다. 이로써 제창된 지 120여 년 만에 사색정리가 처음으로 증명되었습니다.Every planar map is four colorablehttps://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society/volume-82/issue-5/Every-planar-map-is-four-colorable/bams/1183538218.full

다만, 방대한 경우 나누기의 일부를 사람이 아닌 컴퓨터가 확인했기 때문에, "계산기의 동작을 완전히 추적할 수 없는 증명을 수학적 증명이라고 부를 수 있는가"라는 의문이 제기되었고, 이 증명은 당시 큰 논란을 불러일으켰습니다. 그 후 1997년에는 닐 로버트슨 등의 연구팀이 아펠과 하켄의 방법을 정리하여, 컴퓨터로 확인하는 배치를 633가지까지 줄인 더 단순한 증명을 발표했습니다. 컴퓨터를 이용한 수학적 증명도 널리 받아들여지게 되면서, 이 증명은 수학계에서도 빠르게 받아들여졌습니다.

1976년과 1997년의 증명에는, "거대한 그래프를 실제로 4색으로 칠할 경우, '처리 가능한 배치를 1개 찾는다' '그 부분을 제거하여 그래프를 조금 작게 만든다' '다시 처리 가능한 배치를 1개 찾는다'라는 조작을 반복한다"는 공통점이 있습니다. 이는 말하자면, 큰 짐 더미에서 매번 1개만 치우고, 그때마다 더미 전체를 다시 조사하는 것과 같다고 할 수 있습니다. 예를 들어 정점이 n개 있는 그래프의 경우, 이 방법에 의한 채색 알고리즘의 처리에는 O(n2) 정도의 다항식 시간이 필요했습니다. 이는 그래프의 정점 수가 n배가 되면, 검증에 필요한 계산량이 대략 n의 2제곱에 비례하여 늘어납니다.

국립정보学研究所(국립정보학연구소)의 가와라바야시 켄이치 씨, 도쿄대학의 이노우에 유타 씨와 미야시타 아츠유키 씨, 사이먼 프레이저 대학의 보얀 모하르 씨, 덴마크 공과대학의 카르스텐 토마센 씨, 코펜하겐 대학의 미켈 토룹 씨로 구성된 연구 팀은 이 문제에 다른 방향으로 접근했습니다. 기존의 증명에서는 주변과의 연결이 비교적 적은 정점이 모인 장소를 중심으로 처리 가능한 배치를 찾았으나, 가와라바야시 씨 연구 팀은 각 정점이 6개의 정점에 연결되어 삼각형이 규칙적으로 나열되는 등 지금까지 거의 활용되지 않았던 '평평한 영역'까지 탐색 대상을 넓혔습니다. 그 결과, 연구 팀은 8202종류라는 대규모 배치의 집합을 찾아냈습니다. 수만 놓고 보면 1997년의 633종류보다 크게 늘어났기 때문에, 일견 증명이 복잡해진 것처럼 보입니다. 하지만 중요한 것은 그중에서 서로 간섭하지 않는 다수의 배치를 동시에 처리할 수 있다는 점입니다. 비유하자면, 기존의 방법은 많은 짐이 있는 방에서 "버릴 수 있는 물건을 1개 찾는다", "1개 버린다", "다시 방 전체에서 1개 찾는다"라는 작업을 반복하는 것과 같았던 반면, 새로운 방법은 서로 방해가 되지 않는 "버릴 수 있는 물건"을 한 번에 대량으로 찾아낼 수 있어, 1회의 처리로 방의 짐을 일정 비율씩 줄여 나갈 수 있습니다. 이 차이로 인해 1회의 처리로 그래프에서 일정 비율의 정점을 줄일 수 있게 됩니다. 예를 들어, 매번 몇 개씩만 줄이는 경우에는 그래프가 비어 있을 때까지 대량의 반복이 필요하지만, 매번 일정 비율씩 줄일 수 있다면 1000개, 500개, 250개와 같이 급속도로 문제를 줄여나갈 수 있습니다. 그 결과, 4색으로 칠하기 위한 계산량은 기존의 O(n2)에서 O(nlog_n)으로 개선되었습니다. 연구 팀은 이를 'near-linear time', 즉 거의 선형 시간의 4색 채색 알고리즘으로 정의하고 있습니다. 이번 성과는 '4색 정리가 옳다'는 결론 자체를 바꾸는 것은 아닙니다. 또한 컴퓨터를 사용하지 않고 누구나 단시간에 확인할 수 있는 간결한 증명을 찾아낸 것도 아니며, 오히려 컴퓨터로 확인하는 배치의 수는 이전보다 늘어났습니다. 새 증명의 중요한 점은 평면 그래프에는 한 번에 다수의 장소를 처리할 수 있는 구조가 숨어 있음을 밝혀내고, 그 성질을 사용해 4색 정리를 재증명했다는 데 있습니다. 이 성질은 4색 정리 이외에도 응용될 가능성이 있습니다. 연구 팀이 주목한 '평평한 영역'은 평면 그래프뿐만 아니라 도넛 모양의 토러스 등 다른 곡면 위에 그려지는 대규모 그래프에도 나타납니다. 따라서 새롭게 개발된 수법이 곡면 위의 그래프 채색 문제를 비롯한 다른 그래프 이론의 문제를 푸는 도구가 될 것으로도 기대되고 있습니다. 한편 토마센 씨는 이번 성과를 얻은 후에도 최종적으로는 "컴퓨터를 사용하지 않고, 왜 4색만으로 충분한지를 이해할 수 있는 증명"을 찾고 싶다고 말했습니다.

[원문 보기](https://gigazine.net/news/20260911-four-color-theory-new-proof/) | 출처: Gigazine