18세기 프로이센의 도시 쾨니히스베르크에는 프레겔강이 흘렀고, 강 한가운데에는 섬이 두 개, 그리고 그 섬들과 양쪽 강둑을 잇는 다리가 모두 7개 있었어요. 사람들 사이에서는 오래된 궁금증이 하나 있었어요. "이 다리 7개를 각각 딱 한 번씩만 건너서, 모든 다리를 다 지나갈 수 있을까?" 산책을 좋아하던 시민들이 실제로 여러 번 시도해봤지만, 아무도 성공하지 못했어요.
1736년, 수학자 레온하르트 오일러가 이 질문에 정면으로 답을 내놓았어요. 그런데 오일러가 한 일은 다리를 직접 건너본 게 아니었어요. 그는 문제를 완전히 단순화했어요. 육지(강둑과 섬)는 점으로, 다리는 그 점들을 잇는 선으로 바꿔버린 거예요. 이렇게 그리면 쾨니히스베르크 문제는 "이 그림을 연필을 떼지 않고, 같은 선을 두 번 지나지 않으면서 한 번에 그릴 수 있는가?"라는 한붓그리기 문제가 돼요. 이 발상이 바로 오늘날 그래프 이론이라는 수학 분야의 출발점이었어요.
여기서 핵심 개념이 차수예요. 한 지점(땅덩어리)에 연결된 다리의 개수를 그 지점의 차수라고 불러요. 한붓그리기를 하는 도중에 어떤 지점을 그냥 지나쳐만 간다면, 그 지점으로 들어오는 다리 하나와 나가는 다리 하나를 반드시 짝지어 쓰게 돼요. 그러니까 출발점과 도착점이 아닌 지점은 지나갈 때마다 다리를 2개씩 소모하고, 그 지점의 차수는 항상 짝수여야만 해요.
반대로 차수가 홀수인 지점은 딱 두 종류뿐이에요 — 여행을 시작하는 출발점(나가는 다리가 하나 남는 곳)과 여행이 끝나는 도착점(들어오는 다리가 하나 남는 곳). 그래서 홀수점은 전체 그래프에 최대 2개까지만 있을 수 있어요. 홀수점이 0개면 어디서 시작해도 한붓그리기가 가능하고 출발점으로 돌아올 수도 있고, 홀수점이 정확히 2개면 그 두 곳을 각각 시작점과 끝점으로 삼아야만 가능해요. 하지만 홀수점이 3개 이상이면, 그 여러 홀수점을 전부 시작점이나 끝점으로 만들 수는 없으니 한붓그리기는 절대 불가능해요.
쾨니히스베르크의 네 지역이 정확히 이 함정에 걸려 있었어요. 섬 하나는 다리 5개로, 나머지 세 지역은 각각 다리 3개로 연결돼 있었거든요. 5, 3, 3, 3 — 네 지역 모두 차수가 홀수예요. 홀수점이 4개나 되니, 시민들이 아무리 다양한 순서로 시도해도 다리 7개를 한 번씩만 건너서 다 지나가는 건 처음부터 수학적으로 불가능했던 거예요.
이 문제 하나로 오일러는 "점과 선으로 이루어진 관계"를 다루는 그래프 이론을 만들어냈고, 이 아이디어는 지금 우리 일상 곳곳에서 쓰여요. 지도 앱이 최단 경로를 찾는 방식, SNS에서 친구 관계를 분석하는 방식, 인터넷에서 데이터가 라우팅되는 방식 모두 그래프 이론 위에서 작동해요. 300년 전 강가 산책자들의 소소한 궁금증이, 오늘날 우리가 매일 쓰는 기술의 뿌리가 된 셈이에요.
저희 체험 페이지에서는 실제 쾨니히스베르크 다리 지도를 직접 클릭하며 한붓그리기를 시도해볼 수 있고, 다른 도형들로도 연습하면서 어떤 도형은 되고 어떤 도형은 안 되는지 직접 확인할 수 있어요. 마지막에는 각 도형의 차수를 표로 정리해서, 홀수점 개수만 세어보면 미리 답을 알 수 있다는 것도 확인할 수 있어요.