Chứng minh rằng một đồ thị đầy đủ có n đỉnh thì có n( n - 1)/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}\).