Combinatorics/Graph theory problem

Question

(This is a homework problem. I would very much appreciate it if you may provide some constructive hints/ideas.)

Consider a triangle-free graph $G=(V,E)$. Let $n=|V|$ and $m=|E|$.

Define $N(v)$ as the set of vertices that are adjacent to $v$, including $v$ itself.

Prove: There exists a vertex $v$ such that $V(G)\backslash N(v)$ contains at most $m-\frac{4m^2}{n^2}$ edges.

Note: I have seen a proof that any n-vertex triangle-free graph has at most $n^2/4$ edges, where the inequality $m\ge \frac{4m^2}{n^2}$is obtained. I suspected I may use this result in my problem.

Answer 1

Hint:

Let $f : V \to \mathbb{N}$ be defined as $$f(v) = \sum_{u \in V \text{ is adjacent to } v} \deg(u),$$ and prove that the average value of $f$ over $V$ is at least $\frac{4m^2}{n^2}$.

Solution:

Because the graph is triangle-free, $f(v)$ is the number of edges incident to $N(v)$. We want to prove that there exists a vertex $v$ such that $f(v) \geq \frac{4m^2}{n^2}$. To this end we will show that the average value of $f$ over $V$ is at least that much. Observe that $$ n\cdot\sum_{v \in V}f(v) = \left(\sum_{v \in V} 1^2\right) \cdot \left(\sum_{v \in V} \big(\!\deg(v)\big)^2\right) \stackrel{\spadesuit}{\geq} \left(\sum_{v \in V}1 \cdot\deg(v)\right)^2 = 4m^2, $$ where $(\spadesuit)$ is the Cauchy—Schwarz inequality. Therefore, $\frac{1}{n}\sum_{v \in V}f(v) \geq \frac{4m^2}{n^2}$ what concludes the proof.

I hope this helps $\ddot\smile$