Pytający:
Zakładam, że chodzi o grafy proste.
a)
k wierzchołków izolowanych ⇒ n≥k
Dla n=k oczywiście istnieje taki graf (bez krawędzi).
Dla n=k+1 nie istnieje taki graf. Bez krawędzi mamy k+1 wierzchołków izolowanych (a nie
dokładnie k), natomiast po dodaniu jakiejkolwiek krawędzi pozostanie jedynie k−1 wierzchołków
izolowanych.
Dla n≥k+2 istnieje taki graf. Wystarczy połączyć krawędziami n−k wierzchołków tak, aby żaden
nie pozostał izolowany (można to zrobić, bo n−k≥2). Pozostałe k wierzchołków to wierzchołki
izolowane.
b)
Mamy n−k wierzchołków nieizolowanych.
| | (n−k)(n−k−1) | |
Maksymalna liczba krawędzi to |
| . Wtedy graf składa się z k wierzchołków |
| | 2 | |
izolowanych oraz z podgrafu będącego grafem pełnym o n−k wierzchołkach.
Minimalna liczba krawędzi to n−k−1. Wtedy graf składa się z k wierzchołków izolowanych oraz z
podgrafu będącego drzewem o n−k wierzchołkach. Dla n=k ten wzór nie działa, wtedy oczywiście
mamy 0 krawędzi. Zatem uogólniając minimalna liczba krawędzi to max{0,n−k−1}.