HGHC는 graph theory / combinatorics에서 오랫동안 제기되어 왔던 추측을 반증하는 lemma로, 확률론적 방법의 대표적인 예제이다. 확률론적 방법의 진수를 보여주는 lemma라고 생각하는데, 확률론적 방법 전체를 소개하기에는 너무 길고, 이 정리의 증명만 포스트에 싣기로 한다. 아마 wikipedia 수준의 사전 지식 이외에는 필요하지 않을 것이다. Thanks to. claim 0. Introduction 임의의 자연수 t, ut, \ ut, u에 대해 g(G)>tg(G) > tg(G)>t와 χ(G)>u\chi (G) > uχ(G)>u를 동시에 만족하는 그래프 GGG가 존재한다. 여기서 그래프의 girth g(G)g(G)g(G)는 GGG에서 가장 작은 cycle의 크기를 의미하고, χ(G)\chi (G)χ(G)의 경우 g..