Chứng minh rằng một đồ thị đầy đủ có n đỉnh thì có n(n-1)/2 cạnh

Giải Chuyên đề Toán 11 Kết nối tri thức Bài 8: Một vài khái niệm cơ bản

Bài 2.4 trang 40 Chuyên đề Toán 11: Chứng minh rằng một đồ thị đầy đủ có n đỉnh thì có $\frac{n\left(n-1\right)}{2}$ cạnh.

Lời giải:

Do đồ thị đầy đủ nên mỗi đỉnh được nối với n – 1 đỉnh khác, tức là số cạnh là n(n – 1) cạnh.

Tuy nhiên, do ở trên ta đã tính lặp một cạnh 2 lần, nên số cạnh thực tế của đồ thị là $\frac{n\left(n-1\right)}{2}$.