Giải bài tập 2.23 trang 50 chuyên đề Toán 11 Kết nối

Gọi số đỉnh của đồ thị là n.

Theo bài tập 2.4 trang 40 (Bài 8: Một vài khái niệm cơ bản) ta có: Một đồ thị đầy đủ có n đỉnh thì có $\frac{n(n-1)}{2}$ cạnh.

Ta có: $\frac{n(n-1)}{2}\geq 1000 \Leftrightarrow n^{2}-n-2000\geq 0$

$\Leftrightarrow \left[\begin{matrix}x &\leq \frac{1-3\sqrt{889}}{2}\\ \frac{1+3\sqrt{889}}{2} &\leq  x\\\end{matrix}\right.$

Vì n là số tự nhiên dương nên chọn giá trị $45\approx \frac{1+3\sqrt{889}}{2} \leq  x$.

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