BÀI 7. CHO SỐ NGUYÊN DƯƠNG N > 1. KÝ HIỆU T LÀ TẬP HỢP TẤT CẢ CÁC B...

1, 2, . . . , 2n còn E

là tập cạnh; trong đó hai đỉnh u > v được nối với nhau nếu trong

tập hợp A liên kết với T không có cặp có thứ tự ( u, v ) .

Khi đó, theo giả thiết thì với ba số x , y, z thì phải có ít nhất một cặp thuộc A; vì nếu

không, giả sử có cạnh nối cả ba đỉnh x , y, z thì không mất tính tổng quát, giả sử

x > y > z nên G

chứa cả ba cạnh ( x , y ), ( x , z ), ( y, z ) đồng nghĩa với việc khi xét bộ

( x, y, z ) thì cả ba cặp có thứ tự trên không thuộc T, mâu thuẫn.

Suy ra G

không chứa tam giác. Theo định lý Mantel – Turan thì số cạnh của nó sẽ

không vượt quá

²

= n

. Từ đó suy ra số cạnh trong graph bù sẽ ít nhất là

C

− n

= n ( n − 1).

Điều này có nghĩa là có ít nhất n ( n − 1 ) cặp ( u, v ) mà u > v thuộc A.

Chứng minh tương tự thì cũng có ít nhất n ( n − 1 ) cặp ( u, v ) mà u < v thuộc A (ta chỉ

cần xét graph G

= ( V, E

) với quan hệ trong E

là: hai đỉnh u < v được nối với nhau

nếu trong tập hợp A liên kết với T không có cặp có thứ tự ( u, v ) ). Từ đó suy ra trong

T có ít nhất 2n ( n − 1 ) cặp, ta có đpcm.

Nhận xét. Bài toán này thực ra là một cách phát biểu của khéo léo, che giấu đi bản chất

vấn đề của định lý Mantel – Turan. Quan hệ “không có tam giác” phát biểu thông qua

ràng buộc khá rõ, nhưng cần phải xử lý cẩn thận, vì đề cho quan hệ có hướng (trong khi

định lý chỉ áp dụng được cho graph vô hướng). Ta phát biểu rõ ràng lại định lý này cho

trường hợp 3, 4 như sau:

(Mantel – Turan) Một graph G = ( V, E ) có | V | = n và không có 3 đỉnh đôi một nối nhau

thì số cạnh | E | ≤

²

; còn nếu không có 4 đỉnh đôi một nối với nhau thì số cạnh | E | ≤

²

.

Trên thực tế, câu b chỉ là một cách xây dựng ví dụ cho dấu bằng xảy ra ở định lý này.

Còn câu c có thể chứng minh trực tiếp bằng quy nạp. Một số bài toán tương tự: