Combinatorial optimization problem for bipartite graphs Let $G(V_1\cup V_2, E)$ be a simple bipartite graph having $n$ vertices and $m$ edges, such that $|V_1|=|V_2|$ (which implies that $n$ is an even number). Given any node $i \in V_1\cup V_2$, we denote its degree by $d_i$. 
How can we prove that, if $m \le \frac{|V_1||V_2|}{2}=\frac{n^2}{8}$, then we must have $$\sum_{(i,j): i\in V_1,\,j\in V_2} \left(d_i+d_j\right)\le (1-c)n\,m~,$$
where $c$ is a positive constant (bounded away from zero)?

Additionally, I am also interested in finding the minimum value of $c$ satisfying the above inequality. 
 A: Here, let $E$ be the set of edges, $I=V_1$ one side of the graph, $J=V_2$ the other side. Let $S$ be the set of edges $(i,j)$ s.t. both $d(i) \geq .9(n/2)$
and $d(j) \geq .9(n/2)$. Further suppose that $|S| \geq .95|E|$ or we are done.
Now let $I_S$ be the set of $i \in I$ s.t. $i$ is incident to an edge in $S$.
Then each $i \in I_S$ has degree at least $.9(n/2)$ in $G$; as there are only $n^2/8$ edges in $G$ it follows that $|I_S|$ is at most $ \frac{m}{.9(n/2)} = \frac{20m}{9n}$. Likewise let $J_S$ be the set of $j$ s.t. $j$ is incident to an edge in $S$. It follows that $|J_S|$ is at most $\frac{20m}{9n}$. 
Now, for each $i \in I$, let $d_S(i)$ be the number of edges in $S$ that $i$ is incident to. likewise for each $j \in J$ let $d_S(j)$ be the number of edges in $S$ that $j$ is incident to. Then on the one hand, assuming that $|S| \geq .95|E|$:
$$\sum_{i \in I} d_S(i) = \sum_{i \in I_S} d_S(i)  \geq  .95 \sum_{i \in I} d(i) \geq .95 \sum_{i \in I_S} d(i)$$
$$\geq .95 |I_s| \left(.9 \times \frac{n}{2}\right) \ \geq \ |I_S| \times \frac{2n}{5}.$$
On the other hand, $\sum_{i \in I_S} d_S(i) \leq |I_S| \times |J_S|$ (since every edge in $S$ goes from $I_S$ to $J_S$), and $J_S$ is no more than $\frac{20m}{9n}$, which is no greater than $n/3$ for $m \leq \frac{n^2}{8}$.
So $S$ cannot be more than $.95|E|$, which as mentioned in the first paragraph, implies your bound.
