일곱 다리를 한 번씩 건널 수 없다는 것을 어떻게 증명할까?

강의 굽이보다 다리의 연결이 중요해지다

당시 프로이센의 쾨니히스베르크에는 프레겔강을 사이에 둔 네 땅을 잇는 일곱 다리가 있었습니다. 오늘날 칼리닌그라드로 불리는 도시입니다. 세인트앤드루스대학교의 수학사 자료는 당시 도시와 다리 배치, 후대의 도시 지도를 구별해 제시합니다. 이 글에서 다루는 것은 18세기 문제의 연결 구조이며 현재 도시의 통행 안내가 아닙니다.[2]

오일러의 논문은 한국어로 ‘위치의 기하학에 관계되는 문제의 해결’이라고 옮길 수 있습니다. 퍼시픽대학교 오일러 아카이브의 E53 서지는 작성 연도를 1735년, 출판 연도를 1741년으로 기록하며, 『페테르부르크 과학아카데미 논평』 제8권 128~140쪽을 원출처로 제시합니다. 수학사 해설에서는 1736년의 연구로 소개되기도 합니다. 연도가 다른 자료를 읽을 때에는 작성·권호의 연도·실제 인쇄 시점을 구별해야 합니다.[1][3]

핵심 변화는 기하학에서 무엇을 남길지 고르는 데 있었습니다. 다리의 길이가 두 배가 되거나 강이 더 구불구불해져도, 어느 땅과 어느 땅을 잇는지가 같으면 ‘각 다리를 한 번씩’이라는 질문의 답은 유지됩니다. 거리와 각도를 재는 문제에서 연결 관계를 따지는 문제로 관심이 옮겨 간 것입니다.[3]

다만 이 단순화에는 약속이 필요합니다. 한 지역 안에서는 다리 입구 사이를 자유롭게 이동할 수 있고, 강을 넘는 통로는 표시된 다리뿐이며, 모든 다리는 양방향으로 통행한다고 둡니다. 한 지역 안에 지나갈 수 없는 담장이 있다면 땅 하나를 점 하나로 줄이는 방식부터 다시 검토해야 합니다. 어떤 정보를 지웠는지 설명하는 일이 모형을 만드는 첫 단계입니다.

땅은 점으로, 다리는 서로 구별되는 선으로

아래 그림에서는 다섯 다리가 닿는 땅을 가, 나머지 땅을 나·다·라라고 부릅니다. 가와 나 사이에는 다리 1·2, 가와 다 사이에는 3·4, 가와 라 사이에는 5가 있습니다. 나와 라는 6, 다와 라는 7로 연결됩니다. 이 이름과 번호는 이번 설명에서 붙였으며 역사적 다리 이름과는 구별합니다.[4]

점은 땅의 실제 위치나 넓이를 표시하지 않습니다. 선도 강 위 다리의 정확한 모양이 아닙니다. 두 점 사이에 선이 두 개 있다면 서로 다른 두 다리가 있다는 뜻입니다. 보기 편하다고 두 선을 하나로 합치면 일곱 다리 문제가 다섯 다리 문제로 바뀝니다. 그려진 모양을 단순하게 만드는 일과 관계를 삭제하는 일은 다릅니다.

현대 수학에서는 이런 점과 선의 구조를 그래프, 곧 연결망이라고 부릅니다. 한 점에 닿는 선 끝의 개수는 ‘차수’라고 합니다. 이 예에서 가의 차수는 5, 나·다·라의 차수는 각각 3입니다. 같은 두 지역을 잇는 다리도 각각 하나씩 세어야 합니다. 이 용어와 그림은 오늘의 설명 방식이며 오일러의 원문 도판을 그대로 재현한 것이 아닙니다.[4]

그림을 읽으며 선 끝을 모두 세어 보세요. 가에서 5개, 나·다·라에서 3개씩이므로 합은 14입니다. 다리 하나는 서로 다른 두 땅에 끝을 하나씩 제공하므로 일곱 다리의 끝은 2×7=14개여야 합니다. 이 일치는 그림에서 다리를 빠뜨리거나 중복해 센 일이 없는지 확인하는 첫 검사입니다.

질문 1. 다리 1·2를 화면에서 한 줄로 합쳐 그리고 ‘가와 나는 연결되어 있다’만 남기면 원래 질문을 풀 수 있을까요? 해설: 연결 여부는 남지만 다리의 개수가 사라집니다. 각 다리를 정확히 한 번 쓰는 문제에서는 1과 2를 별개로 보존해야 합니다. 단순화한 그림이 무엇을 보존하는지 질문에 맞추어 판단해야 합니다.

중간에 들르는 땅에서는 들어온 뒤 나가야 한다

모든 다리를 한 번씩 건너는 여행이 끝났다고 가정해 봅시다. 출발지도 도착지도 아닌 한 땅을 골라 그곳에 들른 장면만 모읍니다. 다리 하나로 들어왔으면 다른 다리 하나로 나가야 여행이 계속됩니다. 다음에 또 들렀을 때도 들어오는 다리와 나가는 다리가 한 쌍을 이룹니다.

그 땅을 한 번 들르면 두 개, 두 번 들르면 네 개, 세 번 들르면 여섯 개의 다리 끝을 사용합니다. 모든 다리를 써야 하므로 남겨 둔 다리 끝도 없어야 합니다. 따라서 중간 지역의 차수는 짝수여야 합니다. 어느 다리로 먼저 왔는지는 이 계산에 영향을 주지 않습니다. 가능한 모든 순서에 적용되는 이유를 얻은 셈입니다.

출발지에서는 처음 나가는 다리에 앞선 ‘들어옴’이 없습니다. 도착지에서는 마지막 들어오는 다리에 뒤따르는 ‘나감’이 없습니다. 출발지와 도착지가 서로 다르면 이 두 곳만 짝이 없는 끝 하나씩을 가질 수 있습니다. 홀수 차수 지역이 있다면 바로 두 끝자리를 맡아야 합니다.

반대로 출발지로 되돌아오는 여행에서는 첫 출발과 마지막 도착을 서로 짝지을 수 있습니다. 이때는 출발지를 포함해 모든 지역의 차수가 짝수여야 합니다. ‘어디에서 끝나도 된다’와 ‘출발지로 돌아와야 한다’는 조건을 섞으면 같은 지도를 보고도 서로 다른 문제에 답하게 됩니다.[4]

그림에서 살펴볼 것은 어느 칸이 남는가입니다. 가운데 들르는 곳에는 남는 칸이 없고, 출발·도착에는 하나씩 남습니다. 차수가 5인 지역도 똑같이 생각할 수 있습니다. 두 쌍을 만들고 하나가 남으므로 그 지역 역시 여행의 한 끝자리를 요구합니다. 다리가 많아서 어려운 것이 아니라 홀수라는 성질이 결정적입니다.

끝자리는 둘인데, 네 지역이 끝자리를 요구한다

원래 연결망의 차수는 5·3·3·3입니다. 네 지역이 모두 홀수입니다. 각 지역은 들어옴과 나감을 짝지은 뒤 하나가 남으므로 출발지 또는 도착지여야 합니다. 그러나 한 번 이어지는 여행에는 출발지와 도착지, 두 끝자리밖에 없습니다. 네 지역을 그 둘에 모두 배정할 수 없습니다.

이 결론은 특정한 길을 따라가다 막힌 기록과 다릅니다. 아직 시도하지 않은 길도 성공하는 여행이라면 출입 짝짓기 조건을 만족해야 합니다. 원래 연결망은 그 조건에 맞지 않으므로 남은 순서를 더 시험해도 답이 바뀌지 않습니다. 성공했다고 가정한 뒤 반드시 따라오는 조건과 주어진 구조의 충돌을 보인 것입니다.

논증도를 위에서 아래로 읽어 보세요. 먼저 여행의 규칙을 고정하고, 중간 지역의 짝짓기에서 홀수 지역의 수에 관한 제한을 얻습니다. 여기에 실제 그림에서 센 네 홀수 지역을 대조합니다. ‘오래 찾아도 길이 안 보였다’는 경험은 이 증명의 전제로 들어가지 않습니다.

질문 2. 출발지와 도착지를 자유롭게 정하면 네 홀수 지역 중 두 곳만 고르고 해결할 수 있을까요? 해설: 고른 두 지역은 끝자리를 맡을 수 있지만, 나머지 두 홀수 지역은 중간 지역이 됩니다. 그곳에는 짝이 없는 다리 끝이 남습니다. 모든 다리를 사용한다는 규칙이 유지되는 한 자유로운 출발지 선택으로 이 문제를 해결할 수 없습니다.

증명은 규칙에 기대고 있습니다. 강을 배로 건너거나 여행을 중간에 끊어 다른 지역에서 다시 시작하면 ‘한 번 이어지는 여행’이라는 전제가 달라집니다. 새로운 규칙에서 성공하는 사례를 찾아도 원래 증명의 반례가 되지는 않습니다. 반례는 결론만 뒤집는 사례가 아니라 모든 전제도 함께 만족하는 사례여야 합니다.

다리 하나를 빼면 여섯 다리의 길이 열린다

이제 역사적 사실과 구별되는 가상 실험을 해 봅시다. 다리 1만 닫고 나머지 여섯 다리를 한 번씩 건너도록 규칙을 바꿉니다. 가의 차수는 5에서 4로, 나의 차수는 3에서 2로 줄어듭니다. 다와 라는 여전히 3입니다. 홀수 지역은 둘만 남으며 모든 지역은 서로 연결되어 있습니다.

이번에는 길을 직접 제시할 수 있습니다. 다에서 출발해 다리 3으로 가, 2로 나, 6으로 라, 5로 가, 4로 다, 7로 라에 갑니다. 지역 순서는 ‘다 → 가 → 나 → 라 → 가 → 다 → 라’입니다. 가와 다를 여러 번 방문하지만 다리는 3·2·6·5·4·7을 각각 한 번씩 씁니다. 검사 대상이 지역의 방문 횟수인지 다리의 사용 횟수인지 구별해 보세요.

아래 표는 실제 도시의 공사 기록이 아닙니다. 원래 관계도와 다리 1을 제외한 자체 실험을 대조한 것입니다. 차수 합은 ‘원래 일곱 다리’ 열에서 14, ‘다리 1 제외’ 열에서 12가 됩니다. 다리 하나를 닫으면서 두 끝이 함께 사라졌다는 점도 확인할 수 있습니다.

질문 3. 다리 1을 닫은 뒤 나에서 출발해 여섯 다리를 모두 한 번씩 건널 수 있을까요? 해설: 불가능합니다. 홀수 차수인 다와 라가 서로 다른 두 끝자리를 맡아야 합니다. 나의 차수는 2이므로 중간 지역으로 통과해야 합니다. 위에 적은 길을 거꾸로 따라 라에서 출발하는 것은 가능합니다.

‘홀수 지역이 둘이면 가능하다’는 말에는 연결 조건이 포함되어야 합니다. 서로 떨어진 두 삼각형을 그리면 모든 점의 차수가 2여도 한 삼각형에서 다른 삼각형으로 갈 수 없습니다. 여행에 필요한 모든 선이 한 덩어리로 연결되어 있는지 먼저 살펴야 합니다. 다리가 전혀 닿지 않는 점은 이번 여행의 방문 대상에서 제외합니다.

가능한 길의 조건과 길을 만드는 방법은 구별한다

지금까지의 짝짓기는 ‘성공한 길이 있다면 홀수 지역은 0곳 또는 2곳’이라는 방향을 설명했습니다. 이것만으로 그 조건을 만족하는 모든 연결망에서 길이 존재한다는 반대 방향까지 증명한 것은 아닙니다. 불가능성을 판정하는 조건과 가능성을 보장하는 구성이 각각 필요합니다. 현대의 정리는 연결된 유한 무방향 연결망에서 두 방향이 모두 성립한다고 말합니다.[4]

모든 차수가 짝수일 때의 구성 원리를 짧게 따라가 봅시다. 한 점에서 출발해 아직 쓰지 않은 선으로 계속 걷습니다. 출발점 이외의 점에 들어온 순간에는 사용한 끝이 홀수 개가 되므로, 원래 짝수인 끝을 모두 소진할 수 없습니다. 나갈 선이 남습니다. 선이 유한하므로 결국 출발점에서 닫힌 길 하나를 만들 수 있습니다.

그 닫힌 길에 모든 선이 들어 있다면 끝입니다. 빠진 선이 있다면 연결 조건 덕분에 이미 만든 길의 어느 점에서 사용하지 않은 선으로 이어질 수 있습니다. 그 점에서 남은 선으로 또 하나의 닫힌 길을 만든 뒤 기존 길의 해당 방문 자리에 끼워 넣습니다. 한 번의 닫힌 길에서 사용한 끝은 각 점마다 짝수 개이므로 남은 선들의 차수도 짝수입니다. 이 과정을 반복하면 빠진 선을 모두 포함할 수 있습니다.

홀수 차수 점이 정확히 둘일 때는 그 둘 사이에 가상의 선 하나를 더합니다. 두 점이 짝수로 바뀌면 방금의 방식으로 닫힌 길을 만들 수 있습니다. 그 길에서 가상의 선만 잘라 내면 원래 두 홀수 점을 양 끝으로 하는 길이 남습니다. 이것은 현대적 구성 설명이며, 원전의 문구와 증명 순서를 번역한 것으로 소개하지 않습니다.

이 설명을 통해 빠뜨리기 쉬운 전제도 드러납니다. ‘짝수이므로 계속 걸을 수 있다’만으로 모든 선을 이미 방문했다고 결론 내릴 수는 없습니다. 아직 쓰지 않은 작은 고리가 남을 수 있기 때문입니다. 남은 고리를 찾아 기존 길에 끼워 넣는 단계가 전체 완성을 보장합니다. 필요한 조건 하나를 발견했을 때에는 그것만으로 충분한지도 별도로 물어야 합니다.

모든 지역 방문과 모든 다리 사용은 다른 문제다

원래 일곱 다리의 그림에서 ‘나 → 가 → 다 → 라’로 움직이면 네 지역을 한 번씩 방문할 수 있습니다. 다리는 1·3·7만 사용합니다. 지역을 한 번씩 찾는 질문에는 성공했지만, 일곱 다리를 전부 한 번씩 쓰는 질문에는 답하지 않았습니다. 비슷한 말로 보이는 두 요청도 무엇을 빠짐없이 세는지에 따라 문제가 달라집니다.

학교 축제의 네 공간을 가·나·다·라로 정하고, 공간 사이에 통로 번호 카드를 놓아 보세요. 학생 안내팀은 ‘모든 공간 한 번씩 방문’을, 시설 점검팀은 ‘모든 통로 한 번씩 점검’을 맡습니다. 안내팀의 성공 경로를 그대로 점검팀에 넘길 수 있을까요? 위의 세 다리 경로에서 빠진 2·4·5·6번을 표시하면 왜 서로 다른 경로 계획이 필요한지 드러납니다.

이번 활동에서 공간이나 통로의 이름을 바꾸어도 짝짓기 논리는 유지됩니다. 반면 일방통행, 문이 열리는 시각, 통로마다 다른 이동 시간, 점검 후 돌아와야 하는 조건을 추가하면 원래 연결망이 담지 않은 정보가 생깁니다. 홀짝 검사는 이 모든 실무 조건을 해결하는 만능 규칙이 아닙니다. 단순한 연결 모형으로 답할 수 있는 질문을 먼저 정해야 합니다.

다리 길이를 지웠던 이유도 여기서 다시 확인할 수 있습니다. ‘한 번씩 건널 수 있는가’에는 길이가 필요 없었지만 ‘가장 빨리 끝낼 수 있는가’에는 필요할 수 있습니다. 같은 도시에서 만든 도식도 독자의 질문이 바뀌면 담아야 할 정보가 달라집니다. 도식을 평가할 때에는 도시를 얼마나 닮았는지뿐 아니라, 풀려는 질문에 필요한 관계를 보존했는지 살펴보세요.

오늘의 연결망을 옛 문헌과 같은 것으로 보지 않는다

오일러의 다리 논문은 그래프 이론과 위상수학의 초기 역사에서 자주 소개됩니다. 두 분야 전체가 이 한 편에서 완성되었다는 뜻은 아닙니다. 그 뒤의 수학은 서로 다른 문제와 표현, 정의와 증명을 축적했습니다. 이번 글이 주목한 성취는 거리 대신 연결을 남기고, 경로들의 공통 조건으로 불가능성을 설명하는 생각의 전환입니다.[1][3]

이번 확인에서는 오일러 아카이브의 원문 서지·요약, 대학 수학사 해설, 현대 공개 교재의 관련 절을 읽었습니다. 아카이브에 연결된 원문과 번역 PDF는 접근이 완료되지 않아 원전 전문을 판독했다고 기록하지 않습니다. 오일러가 실제 사용한 표기나 문장 순서에 관한 세부 단정도 피했습니다. 본문의 가·나·다·라, 다리 번호, 짝짓기 도해, 다리 하나를 닫은 경로와 학교 활동은 자체 설명입니다.

자료마다 연도가 달리 적힌 경우에도 한 숫자를 조용히 골라 통일하지 않았습니다. 아카이브의 작성·출판 정보와 수학사 해설의 통상적인 1736년 표기를 구별했습니다. 독자가 출처를 다시 확인할 수 있도록 아래에 확인 범위를 남깁니다. 역사 읽기에서도 ‘이 자료가 직접 알려 주는 것’과 ‘설명을 위해 새로 만든 것’을 나누는 태도가 필요합니다.