2 câu hỏi về đồ thị.

[simplekolor]

Chứng minh rằng đồ thị G phẳng, đơn, liên thông có 10 đỉnh, 28 cạnh thì có chứa chu trình độ dài 4.
Chứng minh rằng đồ thị G phẳng, đơn, liên thông có 10 đỉnh, 38 cạnh thì có chứa đồ thị con đầy đủ cấp 4.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[nguyentram]

Câu thứ nhất:
Nhận xét rằng: Nếu tồn tại $2$ đỉnh bất kì có tổng bậc lớn hơn hoặc bằng $12$ thì sẽ tồng tại chu trình độ dài $4$.
Giả sử không tồn tại chu trình độ dài 4 trong đồ thị trên thì tổng bậc $2$ đỉnh bất kì sẽ nhỏ hơn hoặc bằng $11$. Khi đó tổng bậc của các đỉnh trong đồ thị sẽ nhỏ hơn hoặc bằng $\frac{11C ^{2}_{10}}{9}=55$. Do đồ thị có $28$ cạnh nên tổng bậc của đỉnh là $56$. Suy ra mâu thuẫn, vậy trong đồ thị trên phải có chu trình độ dài $4$.
------------------------------
Câu thứ hai:
Xét các đồ thị $10$ đỉnh không chứa $K_{4}$. Khi đó trong mọi đồ thị con gồm 4 đỉnh bất kì của nó, số cạnh tối đa là $5$. Do vậy số cạnh tối đa của đồ thị là $\frac{5C^{4}_{10}}{C^{2}_{8}}=37,5$. Do đó trong đồ thị $10$ đỉnh, $38$ cạnh phải tồn tại $K_{4}$.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]