Given a simple, undirected graph $G=(V,E)$ and $v\in V$ we set $N(v) = \{w\in V:\{v,w\} \in E\}$ and $\text{deg}(v) = |N(v)|$.


The *average degree of the neighbors* of a vertex $v$, or $\text{ad}(v)$, is the average of $\{(deg(x):x\in N(v)\}$. 


The [Friendship Paradox](http://en.wikipedia.org/wiki/Friendship_paradox) states that in many graphs, the share of vertices $v$ with $\text{deg}(v) < \text{ad}(v)$ is more than $50\%$. Of course, there are trivial counterexamples: in the complete graph $K\_n$, this share is $0$. So it appears interesting to consider the share of "popular vertices": We call a vertex $v$ *popular* if $\text{deg}(v) > \text{ad}(v)$.


Question: Can the share of popular vertices be arbitrarily close to 1 in finite graphs?



Average degree of neighbors in a simple graph (-> Friendship paradox)
The answer to the question is Yes.


Consider the complete graph on $n$ vertices with *one edge removed*. It is easy to see that the 2 vertices adjacent to the sole edge that was removed are the only ones that are not popular. So the share of popular vertices is $\frac{n-2}{n}$, which converges to $1$ as $n$ grows large.


