Chủ đề này có 1 trả lời

[nhungvienkimcuong]

Cho $\text{graph}\ \mathcal{G}$ với $9$ đỉnh thỏa với $3$ đỉnh bất kì thì tồn tại một cạnh.Chứng minh rằng $\mathcal{G}$ chứa $\mathcal{K}_4$

[JUV]

Nếu tồn tại $1$ đỉnh nối với ít hơn $5$ đỉnh thì sẽ có ít nhất $4$ đỉnh không nối với đỉnh đó, $4$ đỉnh đó sẽ đôi một nối với nhau.Nếu có $1$ đỉnh $A$ nối với ít nhất $6$ điểm $A_1,A_2,A_3,A_4,A_5,A_6$. Nếu một trong $6$ điểm đó nối với nhiều nhất $2$ trong $6$ điểm thì trong ít nhất $3$ điểm còn lại, các điểm đôi một nối với nhau nên $3$ điểm đó với điểm $A$ tạo $G4$. Nếu tồn tại $1$ điểm $B$ nối với ít nhất $3$ điểm trong $6$ điểm thì trong $3$ điểm đó tồn tại $1$ cạnh, từ đó có $G4$ là $A,B$ và $2$ điểm được nối.Nếu mỗi điểm trong $9$ điểm đó nối với đúng $5$ đỉnh thì tổng số cạnh là $\frac{5\times 9}{2}\notin \mathbb{N}$(vô lí) $\Rightarrow$ $(Q.E.D)$