71.8곳의 물류센터를 모두 연결하는 도로를 개설하려 한다. 필요한 도로의 최소 길이는?

① 19 km

정답: X

여덟 곳을 이으려면 도로 7개가 필요하고 가장 짧게 골라도 23km라 19km로는 다 못 잇는다.

② 21 km

정답: X

짧은 도로부터 골라도 7개를 합하면 23km라 21km로는 여덟 곳을 다 이을 수 없다.

③ 23 km

정답: O

짧은 도로부터 고리가 안 생기게 고르면 E-H 2, F-H 2, E-G 3, C-E 3, A-D 4, B-E 4, B-D 5 → 7개 합 23km.

④ 25 km

정답: X

B-D 5 대신 A-E 7이나 D-G 7로 A·D를 이으면 25km가 된다 — B-D 5가 더 짧다.

⑤ 27 km

정답: X

여덟 곳을 잇는 가장 짧은 길이는 23km이고, 27km는 그보다 긴 연결이다.