# graph: average of average degree of neighbours, is at least the average degree

• Jan 21st 2013, 12:51 AM
evilbu
graph: average of average degree of neighbours, is at least the average degree
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$
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.