2015 Thirteenth IMAR Mathematical Competition

To prove this, let $G$ be a simple graph on $n$ vertices, and let $S$ be a maximal independent set of vertices of $G$. If $v$ is a member of $S$, then $k(v)\le n-|S|$, since $v$ has at most $n-|S|$ neighbours. If a vertex $v$ is not in $S$, then $k(v)\le |S|$, since $k(v)$ is the size of an independent set. Consequently, $$\sum _{v\in V(G)}k(v)\le |S|(n-|S|)+(n-|S|)|S|\le \lfloor n^2/2\rfloor .$$

The complete bipartite graph $K_{\lfloor n/2\rfloor ,\lceil n/2\rceil }$ clearly achieves the upper bound. Achieving the upper bound requires that all of $S$ be adjacent to all of $V(G)\setminus S$ and that $V(G)\setminus S$ be an independent set, so the extremal graph is unique.