어떤 나라에 유한개의 마을이 있다고 하자. 각각의 마을은 일방통행만이 가능한 길로 연결되어 있다. 또한 이 나라의 어떤 두 마을을 선택하더라도 한쪽 마을에서 다른쪽 마을로 가는 길이 존재한다고 하자. (제 삼의 마을을 거쳐서 가는것이 물론 허용된다.) 이 때, 이 나라에 어떤 마을이 존재하여, 이 마을로부터 다른 모든 마을을 갈 수 있음을 증명하여라.
각 마을을 $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}$로부터 모든 마을을 갈 수 있다.
