하드비거–넬슨 — 평면 전체를 몇 색으로 지킬 수 있을까?

1950년 프린스턴 학생이던 에드워드 넬슨이 이 질문을 생각했다. 평면에는 점이 무한히 많지만 규칙은 단 하나다. 단위거리로 연결된 점끼리 같은 색을 금지한다. 작은 모저 방추 그래프만 그려도 3색은 부족해 최소 4색이 필요하고, 평면을 작은 육각형으로 나누면 7색으로 충분하다는 것을 볼 수 있었다. 그래서 수십 년 동안 답은 4·5·6·7 가운데 갇혀 있었다.

2018년 전혀 예상 밖의 돌파가 나왔다. 생물노화 연구자로 더 잘 알려진 오브리 드 그레이가 1,581개 점으로 된 단위거리 그래프를 만들어 4색으로는 불가능, 즉 최소 5색이라는 것을 증명했다. 이후 공동 탐구자들이 더 작은 증명 그래프를 찾았다. 문제는 단숨에 한 칸 전진했지만, 정확한 답은 여전히 5·6·7 중 하나다.

이 난제는 전문가만의 언어로 잠겨 있지 않다. 점을 몇 개 찍고 길이 1인 선을 이어 색칠하다 막히는 순간, 컴퓨터 탐색과 인간의 패턴 감각이 만난다. 드 그레이의 돌파도 “더 복잡한 그림을 붙이면 4색을 궁지에 몰 수 있지 않을까?”라는 조립 실험에서 시작했다.