도시들이 주어져 있고, 각각의 도시에 대해 정확히 세 개의 서로 다른 도시로 갈 수 있는 비행기편이 있다고 한다. 어떤 사람이 이 편로들을 이용해 이 사람의 고향에서 출발해 모든 도시들을 한 번씩만 거쳐 다시 원래 도시로 돌아왔다면 이 루트를 세계 일주라 부른다. 만약 이 도시들에서 세계 일주가 가능했다면, 그 여정과 다른 방법으로 세계 일주가 가능하다. (단, 기존 세계 일주의 여정을 거꾸로 여행하는 것은 제외한다.)
2001년 일본 수학 올림피아드에서 등장했던 문제. 실은 1946년 Cedric Smith가 증명한 것이 그 시초라고 한다. 정리하면, 모든 점의 차수가 3인 그래프 (3-regular graph)에 해밀턴 회로가 존재한다면 반드시 또 다른 해밀턴 회로가 존재한다는 내용이다.
먼저 이미 존재하는 해밀턴 회로에 포함되는 한 변 
를 고정한다. 그리고 이 변을 지나고 
에서 시작하는 모든 해밀턴 경로(회로가 아닌 path)들을 편의상 “좋은 경로”라고 부르도록 한다. 어떤 좋은 경로 
가 
에서 끝난다고 할 때, 가 (1) 도 아니고 (2) 위의 직전의 점도 아닌 어느 한 점 
와 변으로 연결되어 있다면, 에서 시작해 를 따라 까지 간 후, 에서 로 이동하여 다시 원래 경로의 역순으로 쭉 따라간 경로 역시 좋은 경로가 된다. 이렇게 한 좋은 경로 에서 변 
를 이용해 다른 좋은 경로 
를 얻어낼 수 있다면, 역으로 에서도 마찬가지로 변 를 이용해 를 얻을 수 있다.
여기서, 한 그래프 
를 다음과 같이 잡는다. 의 점은 “좋은 경로”들에 해당하고, 만약 한 좋은 경로에서 앞서 설명한 바와 같은 방법으로 다른 좋은 경로를 만들 수 있다면 이 두 좋은 경로에 해당하는 두 점을 변으로 연결한다. (역으로 만드는 것도 가능하므로 방향성 없는 변(undirected edge)으로 그려도 괜찮다) 그러면, 에서 시작해 로 끝나는 좋은 경로 $latex P4에 대해서
- 만약
가 변으로 연결되어 있었다면, 의 에서의 차수는 1이 되고, (앞서 와 인접한 를 찾을 때 총 차수 3에서 (1), (2)에 해당하는 두 경우를 제외하게 됨) - 그렇지 않다면 의 차수는 2가 된다.
그런데 전자의 경우가 바로 변 를 지나는 모든 해밀턴 회로에 해당되며, 일대일대응이 된다. 따라서 그래프 는 좋은 경로들을 꼭지점으로 생각하는 차수가 1 또는 2인 그래프인데, 차수가 1임이 곧 를 포함하는 해밀턴 회로임과 동치인 것이 된다. 차수가 1인 점, 즉 해밀턴 회로는 존재한다고 문제에서 주어졌고, 그래프에서 차수의 합은 짝수이기 때문에 반드시 또 다른 차수가 1인 점(=해밀턴 회로)가 존재하게 되어 증명이 끝난다.
그래프들을 점으로 보는 그래프를 생각하는 재미있는 발상이 인상적이었다. 똑같은 방법을 직접적으로 응용하면 조금 더 일반화된 결과를 얻을 수 있는데, 
가 홀수일 때 -regular 그래프의 임의의 한 변에 대해 그 변을 지나는 해밀턴 회로의 개수가 짝수라는 것.[1] 또한 원래 문제와 동일한 조건에서 해밀턴 회로의 개수는 3개 이상이 됨도 비교적 쉽게 증명할 수 있게 된다.
Elegant Math 계정에서 작성한 트윗 타래를 정리. (2017/07/03)
References
[1] W. T. Tutte, “On Hamiltonian Circuits” Journal of the London Mathematical Society, Volume s1-21, Issue 2, 1 April 1946, Pages 98–101. DOI: 10.1112/jlms/s1-21.2.98
udaqueness 