Czy istnieje graf

[max123321]

Czy istnieje graf, który ma \(\displaystyle{ 7}\) wierzchołków i \(\displaystyle{ 22}\) krawędzie? Graf ma być prosty. Odpowiedź uzasadnij.

[Slup]

Maksymalna liczba krawędzi w grafie prostym o \(\displaystyle{ n}\) wierzchołkach wynosi:
\(\displaystyle{ {n \choose 2}}\)
Wynika to z tego, że każda krawędź w grafie prostym łączy dwa wierzchołki, a zatem krawędzi jest co najwyżej tyle co dwuelementowych podzbiorów zbioru wierzchołków.
Stosując to do Twojej sytuacji uzyskujemy:
\(\displaystyle{ {7 \choose 2}=21<22}\)