Problema 5

Fie un graf neorientat oarecare și o submulțime de $k$ noduri ($k\ge 1$) ale acestuia. Nodurile acestei submulțimi au gradele $2^0, 2^1, \ldots, 2^{k-1}$. Toate celelalte noduri din graf sunt legate la cel puțin un nod din această submulțime. Care este numărul minim, respectiv maxim, de noduri pe care le poate avea graful, în funcție de $k$.

a) $\min=2^{k-1}+1$, $\max=2^k+k-1$; b) $\min=k$, $\max=2^k-1$; c) $\min=k+1$, $\max=2^k+k-1$; d) $\min=2^{k-1}+1$, $\max=2^{k-1}+1$; e) $\min=2^{k-1}$, $\max=2^k+k$; f) $\min=k+2$, $\max=2^{k+1}$.