Sum of degrees at least $n$ There is a graph with $n$ vertices such that for any two vertices $u,v$ without an edge between them, $\deg(u)+\deg(v)\geq n$. What is the smallest possible number of edges in this graph?
As the total number of edges is half of the sum of degrees, it must already hold that there are at least $n/2$ edges (by applying the condition on any missing edge). If there are $s$ disjoint pairs of vertices without a connecting edge, the total number of edges is at least $sn/2$.
 A: This is a sketch that finds the exact solution for even $n$ and gives bounds for odd $n$. As usual, $V$ stands for the vertex set of a Graph, $E$ for the edge set.
Let's say the minimum degree of a vertex of a graph fulfilling the problem's conditon is $k$, and vertext $u$ has degree $k$.
That means the $n-k-1$ vertices that are not $u$ or connected with $u$ have a minimum degree of $n-k$. The remaining $k+1$ vertices (including $u$) have a minium degree of $k$ (it's the global minimum).
That means the sum of all vertices' degrees is
$$\sum_{v \in V} \deg(v) \ge (n-k-1)(n-k) + (k+1)k = n^2-n + 2k^2+(2-2n)k. \tag1 \label{lower}$$
With $n$ fixed, the minimum of the last term is taken at $k=\frac{n-1}2$ (it's a normal quadratic parabola), which means for odd $n$ it really is taken at $k=\frac{n-1}2$, for even $n$ it is taken at $k=\frac n2,\frac n2-1$ to make $k$ integer.
For odd $n$ that means we have
$$\sum_{v \in V} \deg(v) \ge n^2-n-2\left(\frac {n-1}2\right)^2 = \frac{n^2-1}2,$$
so the number of edges in the graph is at least $\frac{n^2-1}4$.
To find an upper bound, let's consider the complete bipartite graph with $\frac{n-1}2$ vertices in each partition, and we add another vertex to it that is connected to all $n-1$ previous vertices. That graph fulfills the problems conditions and has
$$n-1 +\left(\frac {n-1}2\right)^2 = \frac{n^2+2n-3}4$$
edges. That means for odd $n$, the minimal edge count of a graph fulfilling the conditions is bounded as follows:
$$\frac{n^2-1}4 \le |E|_{min} \le \frac{n^2+2n-3}4.$$
For even $n$, using $k=\frac n2$ in \eqref{lower} we get
$$\sum_{v \in V} \deg(v) \ge n^2-n+2\left(\frac {n}2\right)^2 - \left(2-2n\right)\frac n2= \frac{n^2}2,$$
so the edge count is at least $\frac{n^2}4$. OTOH, that is exactly the edge count of the complete bipartite graph with both partitions containing $\frac n2$ vertices, which fulfills the conditions of the problem.
So for even $n$, we have
$$|E|_{min} = \frac{n^2}4.$$
