Sum of maximum size of independent set of neighbors of vertices Let $G$ be a graph such that $|G|=n$, and for each vertex $ v \in G $, let $ f(v) $ be the cardinality of the largest independent subset of neighbors of $ v $. Prove that $ \sum_{v \in G} f(v) \leq n^2/2 $.
I'm not sure what to do here. Any help is greatly appreciated.
 A: Motivating this proof is a construction that achieves $\frac{n^2}{2}$: the complete bipartite graph $K_{n/2,n/2}$.
In this graph, every vertex has a very large independent set among its neighbors: an independent set of size $\frac n2$. We could make that number bigger for some vertices, but this would actually make things worse. Why? Because then the elements of this independent set wouldn't be able to have a large value of $f(v)$.
So that's the argument we want to make rigorous, coupled with the observation that the bound $f(v) \le \deg v$ doesn't actually give anything away in the extremal construction.

Let $M$ be the largest value of $f$ among any of the vertices, and let $v$ be a vertex with $f(v) = M$. 
For the vertices in an independent set of size $M$ among $v$'s neighbors, their degree is at most $n-M$ and therefore the largest value of $f$ that can be achieved among them is $n-M$, too. For the $n-M$ remaining vertices, the largest possible value of $f$ is $M$, by assumption.
So we have $$\sum_{v \in V} f(v) \le M \cdot (n-M) + (n-M) \cdot M = 2M(n-M)$$ which is maximized when $M = \frac n2$, giving $2(\frac n2)^2 = \frac{n^2}{2}$ as an upper bound.
