Bài 4

Cho G là một đồ thị có n đỉnh, thỏa mãn: (i) không đỉnh nào nối với tất cả các đỉnh còn lại; (ii) đồ thị không chứa tam giác; (iii) với mọi hai đỉnh không kề nhau A và B, có đúng một đỉnh C kề với cả hai. Chứng minh mọi đỉnh có cùng bậc và tìm n nhỏ nhất có thể.

Bước 1 trên 6: Chọn một đỉnh và đặt tên các đỉnh kề

Bước trước Bước tiếp

N(A)=\{B_1,\ldots,B_m\},\qquad\deg A=m.

Phân tích chi tiết

Chọn $A$ có bậc $m$ và gọi các đỉnh kề nó là $B_1,\ldots,B_m$ . Hai đỉnh $B_i$ bất kỳ không thể kề nhau, vì khi đó chúng cùng với $A$ tạo thành một tam giác. Với mỗi $i$ , ký hiệu $\deg(B_i)-1$ đỉnh kề $B_i$ ngoài $A$ là $C_{ij}$ .