Đề bài

💧Tìm số đỉnh nhỏ nhất cần thiết để có thể xây dựng một đồ thị đầy đủ với ít nhất 1 000 cạnh.

Lời giải chi tiết

Giả sử G là một đồ thị đầy đủ có n đỉnh và có ít nhất 1 000 cạnh (n ∈ ℕ, n ≥ 2).Vì G là đồ thị đầy đủ nên mỗi cặp đỉnh của G đều được nối với nhau bằng một cạnh, do đó mỗi đỉnh của G đều có bậc là (n – 1).Tổng tất cả các bậc của các đỉnh của G là n(n – 1).Suy ra G có số cạnh là \(\frac{{n\left( {n - 1} \right)}}{2}\)Vì G có ít nhất 1 000 cạnh nên ta có \(\frac{{n\left( {n - 1} \right)}}{2} \ge 1000\)\(\begin{array}{*{20}{l}}{ \Leftrightarrow \;n\left( {n-1} \right)-2000 \ge 0}\\{ \Leftrightarrow \;{n^2}\;-n-2000{\rm{ }} \ge {\rm{ }}0{\rm{ }}\left( * \right)}\end{array}\)Giải bất phương trình (*), ta được \(n \le \frac{{1 - 3\sqrt {889} }}{2} \approx  - 44,22\) (không thỏa mãn) hoặc \(n \ge \frac{{1 + 3\sqrt {889} }}{2} \approx 45,22\) (thỏa mãn).Do n là số tự nhiên nên n nhỏ nhất thỏa mãn là 46.Vậy số đỉnh nhỏ nhất cần thiết để có thể xây dựng một đồ thị đầy đủ với ít nhất 1 000 cạnh là 46 đỉnh.