1ebec223e0dc2bae61abe9e74683716d96d422a0bf029ef3ff57d4b0b7f14e8d8da517cf529f59eaa55048d643ce758f40


n개의 정점을 임의의 순서대로 원형으로 배치하자.

즉, a1a2a3....an (an+1=a1)이다.


그중에 연결이 존재하지 않는 ai와 ai+1을 생각하자. 


이 두점을 제외한 나머지 점들중 aj와 ai가 연결되어있고 ai+1과 aj+1이 연결되어 있는 aj aj+1이 존재한다면 ai aj aj-1 aj-2... ai+2 ai+1 aj+1로 배치를 바꿀수 있고, 이 시행은 연결되어있는 점의 숫자를 2 증가시키고 동시에 연결되어있지 않은 점의 숫자를 2 감소시키므로 유한번 시행하여 모든 점을 연결할 수 있다. (n개의 연결에 도달할수 있음) 이제 이러한 aj aj+1이 존재함을 증명하자.


aj는 가정에의해 n/2개 존재하므로 aj+1또한 n/2개 존재한다. 따라서 전체 집합에서 aj+1, ai,ai+1을 제외한 집합의 원소의 갯수는 n/2 -2이다. ai+1과 연결된점은 n/2개 이상이므로 비둘기집의 원리에 의해 aj+1에는 ai+1과 연결된 점이 적어도 하나 존재한다. 


따라서 이러한 aj aj+1은 항상 존재하고 유한번의 시행끝에 해밀토니안 사이클을 만들수있다.



원래 증명은 읽어봐서 아는데, 내가 한거에 엄밀하지 못한 부분 있는지 궁금함