풀이. 각 마을을 $a_1,\, a_2,\, \ldots,\, a_n$와 같이 나타내자. 또한 임의의 $k = 1,\,2,\, \ldots,\, n$에 대하여, $\abs{a_k}$를 마을 $a_k$ 로부터 갈 수 있는 모든 마을의 개수라 하자. 따라서 이 문제는 $\abs{a_k}=n$인 $k$가 존재함을 증명하는 문제와 같다. 이제 $k_0 = \arg\max_k \abs{a_k}$라 하자. 만약 $\abs{a_{k_0}} < n$이라면, 마을 $a_{k_0}$으로부터 갈 수 없는 마을 $a_l$이 존재할 것이다. 따라서 문제의 가정에 의하여 $a_l$에서 $a_{k_0}$로 가는 길이 존재한다. 하지만 이 경우 (마을 $a_{k_0}$로부터 갈 수 있는 모든 마을은 $a_l$로부터 시작하여 $a_{k_0}$를 거친 뒤에 갈 수 있으므로) $\abs{a_l} > \abs{a_{k_0}}$이 되어 $\abs{a_{k_0}}$의 최대성(maximality)에 대해 모순이 생긴다. 결과적으로 $\abs{a_{k_0}} = n$일 수 밖에 없고 따라서 마을 $a_{k_0}$로부터 모든 마을을 갈 수 있다..