Câu hỏi 18
Cho $n$ là số nguyên dương chẵn và $G$ là đồ thị có $n$ đỉnh, đúng $\frac{n^2}{4}$ cạnh, không có khuyên hay cạnh bội (mỗi cặp không thứ tự gồm hai đỉnh phân biệt được nối bởi $0$ hoặc $1$ cạnh). Một cặp đỉnh phân biệt không thứ tự $\{x,y\}$ được gọi là “thân thiện” nếu chúng có một đỉnh kề chung (tồn tại đỉnh $z$ sao cho $xz,yz$ đều là cạnh). Chứng minh $G$ có ít nhất $2^{\binom{n/2}{2}}$ cặp đỉnh thân thiện không thứ tự.