$\DeclareMathOperator\deg{deg}\DeclareMathOperator\ndeg{ndeg}\newcommand\abs[1]{\lvert#1\rvert}$The friendship paradox goes *most people have fewer friends than their friends have on average*. The original paper Feld - Why your friends have more friends than you do has a simple counter example: (Figure 5, p. 1474).

My question is how exceptional is this example?

Even in some random graph models where some answer is tractable, the analysis of the distribution of a neighbour's degree deals with expectation. That is, in some models it is explicitly shown that *the average difference between the mean number of friends of friends and the number of friends is positive*, which is much less likely to get press attention I think.

Given any graph $G=(V,E)$ and $v\in V$, let $N(v) = \{w\in V:\{v,w\} \in E\}$ and $\deg(v) = \abs{N(v)}$. This is the number of friends of $v$. Now consider $\ndeg(v)= \sum_{w \in N(v)}\deg(w)$, the total friends of friends of $v$ and the distribution of $$ f(v) = \frac{\ndeg(v)}{\deg(v)} - \deg(v). $$ For a friendship paradox, $$ g = \abs{\{v:f(v)>0\}}-\abs{\{v:f(v)<0\}}>0. $$ For the graph pictured above, $$ \{f(v)\}_{v\in \{A,B,C,D,E,F\}}=\left\{ 1,1,-\frac13-\frac13,-\frac13,-\frac13 \right\}. $$ Clearly $g = -2$, and no paradox. But, the mean of $f$ is $1/9>0$.

The mean of $f$ is shown to be positive in the popular configuration model. And this is usually said to be evidence/proof of the friendship paradox. (Tangential question: is $g>0$ in this model?)

Now the question(s):

- Is the mean of $f$ positive for any graph?
- What are some equivalent conditions stated in terms of graph properties to $g >0$?