Hello,

thanks for letting me become a member of this forum.

I would like to ask my very first question here

Let G be a simple graph, with loops, multiple edges and without weighted edges.

For every vertex $\displaystyle v_i$, let $\displaystyle d_i $ denote its degree (number of neighbours), and let $\displaystyle w_i $ denote the average of the degrees of neighbours of $\displaystyle v_i$

Now one should prove that the average $\displaystyle D$ of the $\displaystyle d_i$ is at most the average $\displaystyle W$ of the $\displaystyle w_i$, with equality if and only if the graph is regular (all $\displaystyle d_i $ are equal).

At first, I thought that this was simply related to the friendship paradox, where one considers

$\displaystyle \frac{\sum d_i}{n}\leq X=\frac{ \sum d_i^2}{\sum d_i},$

which follows essentially from Cauchy-Schwarz.

However, I noticed that the above is not quite the same.

For instance, if you take a star graph on 4 vertices, then the average degree $\displaystyle D$ is 1.5, while the number $\displaystyle W$ is 2.5.

The number$\displaystyle X$ from the above is 2, though.

I found a discussion here, where a graph on four vertices is considered, here $\displaystyle D= 2, W=2.4167$ but $\displaystyle X=2.25$

Why your friends have more friends than you: the friendship paradox - Mind Your Decisions

Whenever I tried to prove that $\displaystyle D \leq W$, I started struggling with a $\displaystyle \frac{1}{d_i}$ somewhere that I can't get rid off.

I'm probably missing something rather trivial, but for now I can't see it.

Any ideas?

Many thanks!