Do your friends on average have more friends than you do?

I was watching this TED talk, which suggested that on average your friends tend to individually have more friends than you do. To define this more formally, we are comparing the average number of friends with:

average over each person p of:
    friend popularity, defined as:
    average over each friend f of p:
        number of friends f has

Intuitively, this seems to make sense. After all, if someone has a high number of friends, they will tend to increase friend popularity and affect a high number of people, while those people who decrease friend popularity only affect a low number of people. Does this result hold for all graphs?

Given a person p, let t stand for:

sum over each friend f of p:
    number of friends f has

It is pretty clear that sum(t)=sum(f^2) as a person with f friends has value of f towards their f friends value of t.

We are then trying to determine whether: sum(t/f)>sum(f) holds for all graphs.

Solution 1:

The answer is yes, this holds for any graph (with weak inequality, as Jon points out).

Let's set up some notation. The graph of friendships is $G$. The set of vertices of $G$ (the people) is $V$; the set of edges (the friendships) is $E$. For a person $v$, the number of friends that person has is $\deg v$. The total number of people is $n$.

We want to show that $$\frac{1}{n} \sum_{v \in V} \deg v \leq \frac{1}{n} \sum_{v \in V} \frac{1}{\deg v} \sum_{(u,v) \in E} \deg(u).$$

Cancel the $1/n$'s from both sides. After a little rewriting, we want to show that $$\sum_{v \in V} \sum_{(u,v) \in E} 1 \leq \sum_{v \in V} \sum_{(u,v) \in E} \frac{\deg u}{\deg v}. \quad (*)$$

Let's consider what a given edge $(u,v)$ contributes to each side of $(*)$. On the left, it contributes $1+1=2$. On the right, it contributes $(\deg u)/(\deg v) + (\deg v)/(\deg u)$. For any two positive numbers $x$ and $y$, we have $2 \leq x/y+y/x$. So every edge contributes more to the right hand side of $(*)$ than to the left, and we have the claimed result.

Solution 2:

Trivial comment, but I'm new so I have to post it as an answer: The strict inequality definitely doesn't hold in general, since the sums are equal for regular graphs.