위키백과

램지의 정리: 두 판 사이의 차이

입체적으로 역사 찾아보기
← 이전 편집다음 편집 →
내용 삭제됨 내용 추가됨
시각위키텍스트
183번째 줄:
6개의 꼭짓점을 가지는 완전 그래프의 각 변을 빨강과 파랑으로 칠한다. 한 꼭짓점 ''v''를 보면, 그 꼭짓점에는 5개의 변이 연결되어 있다. [[비둘기집 원리]]에 의해, 적어도 그 중 3개는 같은 색이다. 그 색을 파랑이라고 가정 하고, 그 3개의 변에 연결된 꼭짓점을 각각 ''r'', ''s'', ''t''라고 하자.
 
만약 변 (''r'', ''s''), 변 (''r''t, ''t''r), 변 (''s'', ''t'') 중 어느 하나라도 파랑이면, ''v''와 함께 파란색 삼각형(3개의 꼭짓점을 가지는 완전 그래프)이 생긴다. 만약 어느 하나도 파랑색이 아니면, (''r'', ''s''), (''t ,r'', ''t''), (''s'', ''t'')는 모두 빨강색이므로 빨강색의 삼각형이 생긴다. 그러므로, 6개의 꼭짓점을 가지는 완전그래프 ''K''<sub>6</sub>의 변을 두 가지 색으로 칠하는 경우, 동일한 색의 ''K''<sub>3</sub>를 포함하게 된다. 즉, ''R''(3,3) &le; 6이다.
 
한편, ''K''<sub>5</sub>를 두가지 색으로 칠하는 방법 중에는 동일한 색의 삼각형을 만들지 않는 경우가 존재한다(오른쪽 그림). 그러므로, ''R''(3,3) &gt; 5 이다. 결론적으로 ''R''(3,3)=6
원본 주소 "https://ko.wikipedia.org/wiki/램지의_정리"