Question 83
Let $n$ be a positive integer and let $\mathcal{G}_n$ be the set of all simple graphs on $n$ vertices. For each vertex $v$ of a graph in $\mathcal{G}_n$, let $k(v)$ be the maximal cardinality of an independent set of neighbours of $v$. Determine $\max_{G \in \mathcal{G}_n} \sum_{v \in V(G)} k(v)$ and the graphs in $\mathcal{G}_n$ that achieve this value.