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

그림에서 무엇을 볼까요?

모든 다리를 한 번씩 쓰는 한 여행을 가정한다. 중간 지역에서는 들어옴·나감이 짝을 이룬다. 홀수 지역은 출발·도착 두 곳만 가능하다. 실제 연결망에는 홀수 지역이 네 곳이다. 따라서 주어진 규칙의 여행은 불가능하다.

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

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