Bài 3

Giả sử một tập cặp thỏa các quy tắc trên có nhiều hơn $\frac{(n-1)(n-2)}2$ phần tử, và chọn $n$ nhỏ nhất. Nếu không có cặp xuôi $(i,i+1)$ cũng như cặp vòng $(n,1)$, số phần tử nhiều nhất là $\frac{n(n-3)}2$, nhỏ hơn cận đang xét. Do đó có một cặp biên; đổi nhãn vòng có thể giả sử $(n,1)$ thuộc tập.