쾨니히스베르크의 일곱 다리

18세기 쾨니히스베르크 사람들은 오랫동안 한 가지 수수께끼를 두고 고민했다. 이 도시에는 프레겔강이 흐르는데, 강에는 섬이 두 개 있다. 강을 건너 섬으로 이어지는 다리는 모두 일곱 개이다. 일요일 산책 한 번에 모든 다리를 건너되, 다리마다 한 번씩만 건널 수 있을까? 다리가 강 위에 어떻게 놓여 있었는지 살펴보자.

어느 한 곳에서 산책을 시작해 모든 다리를 한 번씩만 건널 수 있을까? 한번 해 보자. 왼쪽 아래에서 시작해 위로 올라간 다음 차례로 오른쪽으로 가 보자.

다리 일곱 개 가운데 여섯 개를 건넜고, 하나를 빠뜨렸다. 다른 길로 가 볼 수도 있다…

이번에도 쾨니히스베르크의 다리 일곱 개 가운데 여섯 개만 건넜다. 산책 한 번에 모든 다리를 한 번씩만 건너는 것은 불가능해 보인다. 어느 날 유명한 수학자 레온하르트 오일러가 이 문제를 접했다. 유명하다는 말로는 부족하다. 오일러는 자연상수가 그의 이름을 따서 오일러 수라고도 불릴 만큼 수학의 진정한 전설이었다. 오일러는 이 수수께끼를 풀어 보기로 했다. 먼저 다리가 이어지는 섬이나 도시의 각 부분에 이름을 붙였다.

오일러는 다음과 같이 생각했다. 어떤 섬으로 이어지는 다리가 짝수 개이면, 어디에서 시작하든 산책 한 번에 그 다리들을 모두 건널 수 있다. 다리 하나로 섬에 들어가고 다른 다리로 나오면, 아직 건너야 할 다리가 두 개 줄어든다. 다리 하나로 들어가서 다른 다리로 나오려면 다리가 두 개 필요하다. 섬으로 이어지는 다리가 여섯 개이면 그 섬을 세 번 들르게 된다. 예를 들어 섬 B로 이어지는 다리가 다음과 같이 네 개라고 하자.

그러면 어디에서 시작하든 일요일 산책 한 번에 모든 다리를 건널 수 있다. 직접 해 보자! 그림에는 한 가지 경로를 표시했다. 그런데 섬 D에서 섬 B로 이어지는 다리가 하나 더 있다고 하자.

앞에서 고른 경로로는 모든 다리를 한 번씩만 건널 수 없다. 어떤 다리로 섬 B에 돌아왔다가 섬 D로 건너가야 하기 때문이다. 하지만 다른 경로를 고를 수 있다. 섬 B에서 산책을 시작하면 모든 다리를 한 번씩만 건널 수 있다.

섬 B에서 시작해 위쪽의 A 지역으로 갔다가 다리를 건너 B로 돌아오고, C 지역으로 갔다가 다시 섬 B로 돌아온 다음 마지막으로 섬 D로 갔다. 이처럼 다리가 홀수 개인 섬에서 시작하면 그 섬의 다리를 모두 한 번씩만 건널 수 있다. 거꾸로 섬 D에서 시작해 섬 B에서 끝낼 수도 있다.

이렇게 해서 오일러는 모든 다리를 한 번씩만 건너려면 다음 조건이 성립해야 한다는 것을 알아냈다. 모든 섬의 다리가 짝수 개이거나, 다리가 홀수 개인 섬이 두 개여야 한다. 후자의 경우 다리가 홀수 개인 한 섬에서 시작해 다른 섬에서 끝난다. 나머지 섬은 모두 다리가 짝수 개여야 한다. 쾨니히스베르크의 원래 일곱 다리를 살펴보면

모든 섬의 다리가 홀수 개라는 것을 알 수 있다! 섬 A는 3개, B는 5개, C는 3개, D도 3개이다. 그래서 이 수수께끼는 답이 없다. 일요일 산책 한 번에 일곱 다리를 모두 한 번씩만 건너는 것은 불가능하다. 하지만 다리를 아무거나 하나 허물면 곧바로 답이 생긴다. 예를 들어 섬 B와 C 사이의 다리 하나를 허물어 보자.

그러면 섬 B의 다리는 4개, 섬 C의 다리는 2개가 된다. 섬 A와 D의 다리 수는 그대로이다. 이제 다리가 짝수 개인 섬이 두 개, 홀수 개인 섬이 두 개이다. 다리가 홀수 개인 섬 가운데 하나에서 산책을 시작하면 모든 다리를 한 번씩만 건널 수 있다. 그림에서는 섬 A에서 시작해 섬 D에서 끝냈다.

이렇게 레온하르트 오일러는 또 하나의 유명한 수학 문제를 풀었고, 오늘날 그래프 이론이라고 부르는 분야의 기초를 사실상 놓았다. 그를 기려 그래프 이론에서는 모든 변을 한 번씩만 지나는 경로(한붓그리기)가 있는 그래프를 오일러 그래프라고 부른다.