Math Labs

Bài 4

Cho SS là tập gồm mm cặp (a,b)(a,b) của các số nguyên dương với 1≤a<b≤n1\le a<b\le n. Chứng minh có ít nhất m(4m−n2)3n\dfrac{m(4m-n^2)}{3n} bộ ba (a,b,c)(a,b,c) sao cho (a,b),(a,c)(a,b),(a,c) và (b,c)(b,c) đều thuộc SS.
Bước 1 trên 5: Xây dựng bậc của đồ thị
Bước trướcBước tiếp
Di={j:(i,j)∈S or (j,i)∈S},di=∣Di∣D_i=\{j:(i,j)\in S\text{ or }(j,i)\in S\},\qquad d_i=|D_i|
Phân tích chi tiết

Xem 1,…,n1,\ldots,n là các đỉnh và các cặp trong SS là các cạnh. Gọi DiD_i là tập láng giềng của đỉnh ii và di=∣Di∣d_i=|D_i|. Vì mỗi cạnh có hai đầu mút, ∑i=1ndi=2m\sum_{i=1}^n d_i=2m.