모든 선을 한 번씩 그릴 수 있으면, 모든 점도 한 번씩 돌 수 있을까?

한공유점의두삼각형그래프에서오일러순환을구성하고절단점을통한해밀턴순환불가능을증명한다.

강 위에 놓인 실제 현수교와 강변 풍경

사진: DeFacto · CC BY-SA 4.0 · 원본 출처

점A,B,C,D,E와변AB,BC,CA,AD,DE,EA가있다. 두삼각형ABC,ADE는점A만공유한다. 모든변을한번씩지나돌아오는경로와, 모든점을한번씩지나돌아오는경로는각각가능한가? 두번째에서출발점의마지막재방문만허용한다.

E={AB,BC,CA,AD,DE,EA}.E=\{AB,BC,CA,AD,DE,EA\}.

모든변을한번씩지나는순서는A→B→C→A→D→E→A로바로확인된다. A를여러번방문하지만어떤변도두번쓰지않는다. 따라서“한붓그리기”라는말만으로꼭짓점방문조건을읽을수없다.

A를빼면두묶음사이에남은변이없다. A를한번만사용하는순환으로두묶음을모두연결할수없다.

G−A={B,C} ⊔ {D,E},사이 연결변 없음.G-A=\{B,C\}\ \sqcup\ \{D,E\},\qquad\text{사이 연결변 없음}.

A에서출발해첫삼각형을돌면A로돌아와닫혀버린다. 이어다른삼각형을방문하면A를중간에재사용한것이다. 다른점에서출발해도A를지나두번째묶음으로들어간뒤출발묶음으로돌아갈때A가다시필요하다.

교사는변과꼭짓점목록을각각지우며순서를검사하게한다. 원문의정십이면체순환퍼즐을그대로풀거나번역한것이아니라, 방문대상이바뀌면가능성도바뀐다는자체작은그래프를구성했다.

착안 원문: Camins d’Hamilton. 문항의 좌표·조건·논증은 새로 구성했다. 원문 도판이나 활동 지시의 번역이 아니다.