점과 선으로 그린 그림에 색을 칠하는 단순한 놀이가, 반세기 동안 수학자들을 붙잡아 둔 문제로 자라났다. 그 문제는 2019년에야 결말을 맞았다.
여기 점 몇 개와 그것을 잇는 선 몇 개로 된 그림이 있다고 하자. 규칙은 하나다. 선으로 직접 연결된 두 점은 반드시 서로 다른 색으로 칠해야 한다. 이때 색을 가능한 한 적게 쓰고 싶다면, 최소 몇 가지 색이면 충분할까?
장난처럼 들리는 이 질문은 수학에서 가장 오래되고 까다로운 주제 중 하나다. 그리고 이 색칠 놀이에는, 1966년에 한 수학자가 제기한 뒤 50년 넘게 아무도 증명하지도 반증하지도 못한 추측 하나가 숨어 있었다. 결론부터 말하면 — 그 추측은 틀렸다. 하지만 틀렸다는 사실을 보이는 데 필요한 반례가 어찌나 거대했는지, 처음 발견된 것은 우주 전체의 입자 수보다도 압도적으로 큰 규모였다. 그 이야기를 천천히 따라가 보자.
먼저 용어 하나를 정리해야 한다. 수학자들이 말하는 그래프(graph)는 학교에서 배우는 그 그래프 — 가로축과 세로축을 그리고 함수를 그리는 그림 — 이 아니다. 같은 단어를 전혀 다른 두 가지에 쓰는 탓에 혼란스럽지만, 지금부터 다룰 그래프는 대부분의 과학 분야에서 네트워크(network)라고 부르는 것이다.
그래프는 그저 점들의 모임이고, 그 점들 중 일부가 선으로 연결되어 있는 구조다. 점을 꼭짓점(vertex) 또는 노드(node)라 하고, 점을 잇는 선을 간선(edge)이라 부른다. 어떤 점들은 연결되어 있고, 어떤 점들은 연결되어 있지 않다. 그게 전부다. 지하철 노선도, 친구 관계, 인터넷 연결 — 무언가가 무언가와 이어져 있는 상황이라면 모두 그래프로 그릴 수 있다.
이제 색칠을 시작해 보자. 규칙은 이미 말했다. 간선으로 연결된 두 꼭짓점은 다른 색이어야 한다. 아래 그림에서 직접 해 보자.
이렇게 어떤 그래프를 규칙에 맞게 칠하는 데 필요한 색의 최소 개수를 채색수(chromatic number, 彩色數)라 부른다. 위 그래프의 채색수는 3이다. 그래프 이론에서 가장 자주 던지는 질문이 바로 이것이다. "이 그래프는 최소 몇 가지 색이 필요한가?"
'점에 색칠하기'라는 말이 추상적으로 들린다면, 같은 문제가 얼마나 현실적인 모습으로 변장해 나타나는지 보자.
150여 년 전 사람들은 이미 비슷한 고민을 하고 있었다. 지도를 색칠할 때, 국경을 맞댄 두 나라(또는 주)가 같은 색이 되지 않으려면 몇 가지 색이 필요할까? 언뜻 점도 선도 없으니 그래프 문제처럼 보이지 않는다. 하지만 변환은 간단하다. 각 지역을 점 하나로 두고, 두 지역이 국경을 맞대고 있으면 그 두 점을 선으로 잇는다. 그러면 '국경을 맞댄 지역은 다른 색으로'라는 지도 문제가, '연결된 점은 다른 색으로'라는 그래프 색칠 문제와 정확히 같아진다.
이와 관련해 유명한 결과가 있다. 평면 위에 그릴 수 있는 어떤 지도든 네 가지 색이면 항상 칠할 수 있다는 '4색 정리'다. 사람들은 이를 1800년대부터 추측했지만, 증명은 1970년대에야 컴퓨터의 방대한 계산을 동원해서야 이루어졌다. 손으로는 도저히 확인할 수 없는 수많은 경우를 기계가 일일이 점검한, 수학 역사상 손꼽히는 사건이었다.
스도쿠도 위장한 색칠 문제다. 9×9 칸에 1부터 9까지의 숫자를, 각 가로줄·세로줄·굵은 3×3 상자마다 모든 숫자가 정확히 한 번씩 들어가도록 채우는 퍼즐이다. 이것을 색칠 문제로 바꾸려면, 숫자 1부터 9까지를 아홉 가지 색으로 생각하면 된다. 각 칸을 점으로 두고, 같은 숫자가 될 수 없는 칸들 — 즉 같은 줄, 같은 열, 같은 상자에 있는 칸들 — 을 전부 선으로 잇는다. 그러면 이 거대한 그래프를 아홉 가지 색으로 규칙에 맞게 칠하는 것이, 스도쿠를 푸는 것과 완전히 같은 일이 된다.
색칠 문제는 "사이가 나쁜 것들을 떼어 놓기"의 수학이다. 점은 무언가를 뜻하고, 간선은 "이 둘은 같은 자리에 두면 안 된다"는 금지 표시다. 색은 자리(또는 시간대·숫자·주파수)이고, 색칠은 모든 금지를 지키면서 가능한 한 적은 자리로 모두를 배치하는 일이다. 지도의 인접 국가, 스도쿠의 같은 줄, 시험 시간표에서 한 학생이 동시에 볼 수 없는 두 과목 — 전부 같은 골격이다.
이제 색칠이 어디에 쓰이는지 감을 잡았으니, 한 단계 더 들어가 보자. 이번 이야기에는 50년 추측의 핵심이 들어 있다.
당신이 손님을 여러 날에 나누어 초대한다고 하자. 한 날에 모인 사람들은 적어도 한 가지 공통 화제로 즐겁게 대화할 수 있기를 바란다. 각 날짜를 색이라고 두면, 이것은 색칠 문제가 된다. 다만 규칙이 조금 뒤집힌다. 우리는 서로 잘 통하지 않는 두 사람을 다른 날로 떼어 놓고 싶으므로, 공통 화제가 없는 두 사람을 간선으로 잇는다. 그래야 색칠로 그들이 서로 다른 색(날짜)에 배정되기 때문이다.
손님들이 가진 정보가 전공 하나뿐이라고 해 보자. 전공이 비슷하면 할 이야기가 있고, 너무 동떨어지면 어색하다. 전공이 안 맞는 쌍만 선으로 이으면 아래 왼쪽 같은 그래프가 나온다. 그런데 우리는 사람들의 취미도 알고 있다. 취미가 통하면 그것대로 또 대화가 된다. 취미 그래프는 아래 오른쪽이다.
그런데 실제 손님은 전공과 취미를 둘 다 가진 사람들이다. "사진이 취미인 물리학자", "바둑을 두는 요리사"처럼 말이다. 전공 네 가지와 취미 세 가지를 짝지으면 모두 4 × 3 = 12가지 유형의 손님이 생긴다. 여기서 벌써 곱셈의 냄새가 난다.
이 12명을 하나의 그래프로 묶으려면 어떻게 이어야 할까? 우리가 원하는 것은 "공통 화제가 하나라도 있는 사람은 같은 날 모으기"다. 그러니 공통 화제가 전혀 없는 두 사람 — 전공도 안 통하고 취미도 안 통하는 두 사람 — 만 선으로 잇는다. 즉 두 손님 (전공 A, 취미 X)와 (전공 B, 취미 Y)는, 전공 그래프에서 A와 B가 이어져 있고 동시에 취미 그래프에서 X와 Y가 이어져 있을 때만 간선으로 연결된다.
수학자들은 이렇게 만들어진 그래프를 두 그래프의 텐서곱(tensor product, 곱 그래프)이라 부르고, 곱셈을 뜻하는 기호 ×를 써서 나타낸다. 두 그래프를 각각 G, H라 하면 그 텐서곱은 G × H다. (수학에서 그래프는 거의 항상 G와 H로 부르는 관습이 있다.)
이 12명짜리 그래프를 색칠하는 가장 손쉬운 방법은, 앞서 이미 칠해 둔 색칠을 그대로 빌려 오는 것이다. 두 가지 길이 있다.
하나는 손님들의 전공은 무시하고 취미만 보는 것이다. 등산을 좋아하는 사람은 전공이 무엇이든 모두 빨강, 바둑이나 사진을 좋아하는 사람은 모두 노랑. 위 그림이 바로 이 방식이다. 다른 하나는 거꾸로 취미는 무시하고 전공만 보는 것이다. 물리학자와 요리사는 모두 빨강, 역사학자와 작곡가는 모두 노랑. 어느 쪽이든 두 가지 색이면 규칙을 어기지 않고 칠해진다.
취미만 보고 칠한 색이 규칙을 어기지 않는 이유는 간단하다. 곱 그래프에서 두 사람이 선으로 이어졌다는 것은 "취미도 안 통한다"는 뜻을 포함한다. 그런데 취미가 안 통하는 두 사람은 취미 그래프에서 이미 다른 색으로 칠해져 있었다. 그러니 곱 그래프에서도 둘은 자동으로 다른 색이 된다. 전공만 보고 칠한 경우도 똑같다. 그래서 두 입력 그래프 중 더 적은 색으로 칠해지는 쪽의 색칠을 베껴 오면, 곱 그래프는 언제나 그만큼의 색으로 칠해진다.
이 사실을 기호로 적으면 다음과 같다. χ(G)를 그래프 G의 채색수라 할 때,
왼쪽은 곱 그래프를 칠하는 데 필요한 색의 수, 오른쪽은 두 입력 그래프의 채색수 중 더 작은 쪽이다. 부등호는 "곱 그래프는 적어도 그 정도로는 칠해진다"는, 방금 본 게으른 색칠이 보장하는 사실이다. 여기까지는 누구나 금방 납득할 수 있다.
진짜 질문은 여기서 시작된다. 게으른 색칠이 정말 최선일까? 두 정보를 영리하게 합치면, 더 적은 색으로 칠할 수는 없을까?
방금 본 작은 예시에서는 게으른 색칠이 분명히 최선이었다. 간선이 있는 이상 최소 두 색은 필요하니까. 하지만 그래프가 복잡해지면 이야기가 달라진다. 가령 전공 그래프는 8가지 색이 필요하고 취미 그래프는 13가지 색이 필요하다고 하자. 게으른 색칠로는 곱 그래프를 8가지 색으로 칠할 수 있음을 안다. 그런데 혹시, 어떤 기발한 방법으로 그것을 단 4가지 색으로 칠할 수는 없을까?
1966년, 한 수학자가 박사 논문에서 이 질문에 단호한 답을 내놓았다. 그보다 나은 색칠은 없다는 것이다. 곱 그래프의 채색수는 언제나 두 입력 그래프 채색수 중 작은 쪽과 정확히 같다 — 부등호가 아니라 등호라는 주장이었다. 이것이 그의 이름을 딴 헤데트니에미 추측(Hedetniemi's conjecture)이다.
달리 말하면, 두 그래프를 곱해도 색이 예상보다 적게 줄어드는 일은 결코 일어나지 않는다는 단언이다. 아무리 영리하게 합쳐도, 게으른 색칠 이상으로 색을 아낄 수는 없다는 것.
두 그래프를 텐서곱하면 채색수가 더 작은 쪽을 따라간다. 결코 그 아래로는 내려가지 않는다.
이 추측이 놀라운 이유는, 게으른 색칠이 사실 많은 정보를 버리고 있기 때문이다. 전공만 보고 칠하면, 전공은 안 맞지만 취미가 잘 통해서 같은 날 모여도 됐을 사람들을 공연히 떼어 놓게 된다. "명상을 즐기는 수학자"와 "명상을 즐기는 음악가"가 같은 날 와도 좋았을 텐데, 전공만 따지느라 갈라 버리는 식이다. 그러니 두 정보를 모두 활용하면 날을 더 줄일 수 있을 것 같다는 직관이 자연스럽게 든다. 게으른 색칠은 말 그대로 게으른 선택처럼 보인다.
그런데 — 그렇게 색이 줄어드는 실제 사례를 만드는 일이 도무지 되지 않았다. 수십 년이 흘렀고, 많은 수학자가 매달렸지만, 누구도 추측을 증명하지도 반증하지도 못했다. 부분적인 성과는 있었다. 두 입력 그래프가 충분히 단순해서 3가지 색 이하로 칠해지는 경우라면 추측이 참임이 1985년에 증명되었다. 하지만 딱 거기까지였고, 그 너머는 벽이었다.
2019년 봄, 한 수학자가 단 다섯 쪽 남짓한 짧은 논문을 인터넷에 올렸다. 제목은 간결했다. "헤데트니에미 추측에 대한 반례들." 그는 추측이 틀렸음을 보였다. 곱 그래프의 채색수가 두 입력 그래프 채색수의 최솟값보다 실제로 더 작아질 수 있는 그래프 쌍이 존재한다는 것이었다. 게으른 색칠은 최선이 아니었다.
그가 사용한 도구의 핵심에는 지수 그래프(exponential graph, 指數그래프)라는 발상이 있다. 어떤 그래프 G와 색의 팔레트를 정한 다음, G를 칠하는 모든 가능한 방식 하나하나를 새로운 점으로 삼아 또 다른 그래프를 만드는 것이다. 여기서 '모든 방식'은 규칙을 지킨 색칠뿐 아니라, 연결된 점이 같은 색이어도 괜찮은, 그냥 점마다 아무 색이나 칠한 경우까지 전부 포함한다.
왜 '지수'라는 이름이 붙었을까? 색이 네 가지이고 점이 100개라면, 색칠 방식의 수는 4를 100번 곱한 값 — 4의 100제곱이다. 점이 늘어날수록 색칠의 가짓수는 지수적으로 폭발한다. 그래서 이 보조 그래프의 점의 개수가 천문학적으로 커진다.
그는 원래 그래프와 색의 개수를 딱 알맞게 고르면, 그 그래프와 지수 그래프를 텐서곱했을 때 결과물이 두 입력 그래프 어느 쪽보다도 적은 색으로 칠해짐을 증명했다. 다만 그는 이 숫자들을 굳이 작게 다듬으려 하지 않았다. 반례 하나만 있으면 충분했으니, 계산이 깔끔하게 떨어지도록 숫자를 넉넉하게 키워 버렸다. 수학자들이 반례를 만들 때 흔히 쓰는 전략이다.
그 결과 그가 묘사한 그래프는 상상하기 어려울 만큼 거대했다. 원래 그래프부터가 4의 100제곱 규모의 점을 가졌고, 지수 그래프는 무려 4의 1만 제곱가량의 점을 가졌다. 4의 1만 제곱은 대략 1 뒤에 0이 6,000개쯤 붙는 수다. 참고로, 관측 가능한 우주 전체에 있는 입자의 수는 대개 1 뒤에 0이 80개 정도로 추정된다.
당연히 누구도 이 그래프를 종이에 그릴 수는 없다. 그러나 중요한 것은 따로 있었다. 반례가 이렇게 크다는 사실이, 반례가 반드시 이만큼 커야 한다는 뜻은 아니라는 점이다. 추측이 거짓임을 보이려고 안전하게 크게 잡았을 뿐, 훨씬 작은 반례가 어딘가에 숨어 있을 수 있었다. 그래서 추측이 무너진 직후, 수학자들의 다음 질문은 분명했다. 반례는 얼마나 작아질 수 있는가?
여기서 수학 특유의 협력이 시작된다. 반례가 존재한다는 사실이 알려지자, 여러 수학자가 같은 방법을 다듬고 단순화하며 반례의 규모를 차례차례 줄여 나갔다. 흥미롭게도 반례가 작아질수록 증명은 오히려 더 짧고 읽기 쉬워졌다.
이 진전을 가늠하려면 'c-색 버전'이라는 표현이 편하다. 두 그래프가 각각 c가지 색으로는 칠해지지 않는데, 둘의 곱은 c가지 색으로 칠해지는 경우 — 이것이 c에 대한 반례다. c가 작을수록 더 단순하고 더 놀라운 반례다.
그리하여 '어떤 c에 대해 추측이 성립하는가'라는 물음은 완전히 닫혔다. c가 3 이하면 추측은 참이고, 4 이상이면 거짓이다. 다시 말해, 채색수가 각각 5인 두 그래프인데도 그 곱은 4가지 색으로 칠해지는 — 게으른 색칠보다 한 색을 아끼는 — 쌍이 실제로 존재한다. 이런 가장 작은 반례조차 점의 개수가 수천 개에 이르지만, 적어도 종이 위에 원리를 설명할 수 있는 규모로는 내려온 셈이다.
추측이 거짓으로 판명되면서, 더 미묘한 질문 하나가 전면에 떠올랐다. 채색수가 각각 n인 두 그래프를 곱했을 때, 그 결과의 채색수가 최소 얼마까지 작아질 수 있는지를 f(n)이라 부르자. 헤데트니에미 추측은 "언제나 f(n) = n"이라는 주장과 같았고, 우리는 이제 그것이 틀렸음을 안다. 즉 f(n)은 n보다 작아질 수 있다.
그렇다면 곱 그래프의 채색수는 입력을 키울수록 얼마든지 따라서 커지는가, 아니면 어떤 한계에 부딪혀 멈추는가? 이것이 약한 헤데트니에미 추측(Weak Hedetniemi Conjecture)이며, 여전히 미해결이다. 놀라운 사실은, 만약 f(n)이 어떤 값에서 멈춘다면 그 값은 9를 넘을 수 없다는 점이다. 곱 그래프가 아무리 많은 색을 잡아먹는 입력으로부터 만들어져도, 그 채색수가 무한히 커지지 않는다면 결국 한 자릿수 어딘가에 갇힌다는 뜻이다.
지금까지 알려진 바로는, f(n)이 적어도 n의 절반 수준까지는 떨어질 수 있다. 그러나 그것이 무한히 커지는지, 아니면 어떤 작은 수에서 영원히 멈추는지는 아무도 모른다. 50년 묵은 추측 하나가 무너진 자리에서, 더 깊은 질문이 새로 자라난 셈이다.
이 추측은 '유한한' 그래프에 대한 것이었다. 점이 무한히 많은 그래프로 넓히면 이야기가 완전히 달라진다. 각각 무한히 많은 색이 필요한 두 그래프인데도, 그 곱은 셀 수 있을 만큼의 색으로 칠해지는 사례가 이미 1985년에 알려져 있었다. 무한의 세계에서는 직관이 더 일찍, 더 크게 어긋난다.
이 이야기가 흥미로운 까닭은 결말이 '거짓'이기 때문이다. 반세기 동안 수많은 수학자가 참이라고 믿고 증명에 매달렸지만, 자연은 다른 답을 숨겨 두고 있었다. 더 흥미로운 것은, 그 답을 처음 내놓은 반례가 우주를 종이 삼아도 그릴 수 없을 만큼 거대했다는 점, 그리고 뒤이은 수학자들의 손길이 그것을 종이 위 그림에 가까운 크기까지 깎아 냈다는 점이다.
점과 선에 색을 칠하는 단순한 놀이는, 알고 보면 지도와 시간표와 퍼즐을 관통하는 골격이었고, 그 안에는 반세기를 버틴 질문과 지금도 답을 기다리는 질문이 함께 들어 있었다. 좋은 추측은 참이든 거짓이든 그 자체로 새로운 길을 연다 — 이 색칠 문제가 보여 준 것이 바로 그것이다.