Q:

Graph Theory. Prove that $\sum_{v}^{} \frac{1}{1+d(v)} \ge \frac{n^2}{2e+n} $

Let e denote the number of edges and n the number of vertices. We can assume that the graph G is simple. Prove that
$\sum_{v}^{} \frac{1}{1+d(v)} \ge   \frac{n^2}{2e+n}   $
Any help/hints would be very much appreciated!

A:

Recast the right-hand side as follows:
$$\frac{n^2}{2e+n} = \sum_v\frac{n}{2e+n} = \sum_v \frac{1}{1+ \frac{2e}{n}}.$$
From the handshaking lemma, it follows that $\frac{2e}{n} = \overline{\delta}$, the average degree. Instead of working with the above quantity, we work with the harmonic mean, which is incidentally equal to the arithmetic mean since we are summing over identical quantities:
$$\frac{n}{\sum_v \frac{1}{1+ \overline{\delta}}} = 1+\overline{\delta}=\frac{\sum_v(1+\overline{\delta})}{n}.$$
Notice that since $\overline{\delta}$ is the average degree, we also have
$$\frac{\sum_v(1+\overline{\delta})}{n} = \frac{\sum_v(1+\delta(v))}{n}.$$
By the arithmetic-harmonic inequality, we therefore have
$$\frac{\sum_v\left(1+\delta(v)\right)}{n} \ge \frac{n}{\sum_v\frac{1}{1+\delta(v)}}.$$
Putting everything together, we finally have
$$\frac{n}{\sum_v \frac{1}{1+ \overline{\delta}}} \ge \frac{n}{\sum_v\frac{1}{1+\delta(v)}}.$$
Cancelling $n$s and taking the reciprocal yields the desired inequality. Incidentally, we have also shown that equality occurs if and only if the graph is regular through the equality case of the arithmetic-harmonic inequality.

