Câte muchii are un graf complet cu n vârfuri?

n(n − 1)/2: fiecare dintre cele n vârfuri este legat de celelalte n − 1, iar fiecare muchie a fost numărată de două ori.

Un graf complet are muchie între oricare două vârfuri distincte. Numărul de muchii este

n(n − 1) / 2

Fiecare dintre cele n vârfuri este legat de celelalte n − 1, ceea ce dă n(n − 1) capete de muchii. Dar fiecare muchie a fost numărată de două ori, o dată de la fiecare capăt, deci împarți la 2. Pentru 5 vârfuri ies 10 muchii, pentru 10 ies 45.

Este și numărul maxim de muchii pe care le poate avea un graf neorientat cu n vârfuri, iar fiecare vârf are gradul n − 1.

Alte două calcule din aceeași familie, cerute des la Subiectul I:

• numărul minim de muchii ca un graf cu n vârfuri să fie conex: n − 1 (un arbore);
• numărul maxim de muchii ca un graf cu n vârfuri să fie neconex: (n − 1)(n − 2)/2. Izolezi un vârf și faci restul complet. Cu o muchie în plus, graful e obligatoriu conex.

Lecția despre grafuri neorientate le deduce pe toate din suma gradelor.

Lecția care merge mai departe: Grafuri neorientate: noțiuni