18세기 프로이센의 쾨니히스베르크라는 도시에는 강을 가로지르는 일곱 개의 다리가 있었습니다. 당시 시민들은 산책을 즐기며 한 가지 흥미로운 질문을 던졌습니다. 바로 어느 지점에서 출발하든 일곱 개의 다리를 단 한 번씩만 건너서 모든 다리를 지날 수 있는가 하는 문제였습니다. 많은 이들이 직접 다리를 건너며 시도해 보았지만, 누구도 명쾌한 해답을 찾지 못했습니다. 이 소박한 산책길의 고민은 훗날 수학의 역사를 바꾸는 거대한 질문의 시작이 되었습니다.

수학자 레온하르트 오일러는 이 문제를 해결하기 위해 지도를 단순화하는 혁신적인 방법을 고안했습니다. 그는 복잡한 지형 대신 섬과 육지를 꼭짓점으로, 다리를 변으로 표시했습니다. 이것이 바로 현대 수학과 컴퓨터 공학의 핵심인 '그래프 이론'의 탄생입니다. 오일러는 문제의 본질이 지형의 구체적인 모양이 아니라, 꼭짓점들이 변으로 어떻게 연결되어 있는지에 있다는 사실을 꿰뚫어 보았습니다. 이러한 추상화 과정은 복잡한 현실을 수학적 구조로 변환하는 강력한 도구가 되었습니다.

오일러는 각 꼭짓점에 연결된 변의 개수에 주목했습니다. 그는 한 꼭짓점에 연결된 변이 홀수 개인 '홀수점'의 개수가 문제 해결의 열쇠임을 발견했습니다. 어떤 경로를 따라 다리를 건널 때, 중간에 거쳐 가는 꼭짓점은 반드시 들어오는 변과 나가는 변이 쌍을 이루어야 하므로 짝수 개의 변이 필요합니다. 따라서 모든 다리를 한 번씩만 건너려면 홀수점이 아예 없거나, 시작점과 끝점이 되는 딱 두 개만 존재해야 합니다. 쾨니히스베르크의 경우 네 개의 꼭짓점이 모두 홀수점이었기에 불가능하다는 결론에 도달했습니다.

단순하게 모든 경우의 수를 따져보는 방법도 있습니다. 일곱 개의 다리를 건너는 방향을 고려하면 총 128가지의 경우의 수가 나오는데, 이를 일일이 확인하는 것은 매우 번거롭지만 불가능한 일은 아닙니다. 하지만 다리의 개수가 늘어날수록 상황은 급격히 달라집니다. 수학적 통찰 없이 단순 반복으로 문제를 해결하려 한다면, 데이터가 조금만 복잡해져도 인간이나 컴퓨터가 감당할 수 없는 수준에 이르게 됩니다. 오일러의 해법이 위대한 이유는 바로 이 비효율성을 단숨에 제거했기 때문입니다.

수백 개의 다리가 있는 복잡한 도시에서도 오일러의 풀이법은 단 몇 분 만에 명확한 답을 제시해 줍니다.

이러한 수학적 원리의 위력은 이탈리아 베네치아의 사례에서 극명하게 드러납니다. 베네치아에는 무려 420개의 다리가 있는데, 이를 단순 계산으로 확인하려면 우주의 원자 수보다 많은 경우의 수를 따져야 합니다. 사실상 영겁의 시간이 걸리는 일입니다. 그러나 오일러의 그래프 이론을 적용하면 단 몇 분 만에 모든 다리를 한 번씩 건널 수 있는지 판별할 수 있습니다. 이처럼 수학은 복잡한 세상을 관통하는 질서를 찾아내어, 불가능해 보이는 문제를 해결 가능한 영역으로 이끌어줍니다.