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 , let denote its degree (number of neighbours), and let denote the average of the degrees of neighbours of
Now one should prove that the average of the is at most the average of the , with equality if and only if the graph is regular (all are equal).
At first, I thought that this was simply related to the friendship paradox, where one considers
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 is 1.5, while the number is 2.5.
The number from the above is 2, though.
I found a discussion here, where a graph on four vertices is considered, here but
Why your friends have more friends than you: the friendship paradox - Mind Your Decisions
Whenever I tried to prove that , I started struggling with a 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!