*Context: this question is a translation of a common informal phrasing of the friendship paradox ("Most people have fewer friends than most of their friends"). Note that the question is similar to, but distinct from, [Average degree of neighbors in a simple graph (-> Friendship paradox)](https://mathoverflow.net/questions/205848/average-degree-of-neighbors-in-a-simple-graph-friendship-paradox).*


Given a simple graph $G=(V,E)$ define:


* $\mathrm{N}(v) = \{w\in V:\{v,w\} \in E\}$, the neighbors of a vertex.
* $\mathrm{deg}(v) = |\mathrm{N}(v)|$, the degree of a vertex.
* $\mathrm{pop}(v) = |\{w \in \mathrm{N}(v) : \text{deg}(v) > \text{deg}(w)\}|$, the popularity of a vertex (*i.e. the number of neighbors with lower degree*).


A vertex is said to be **popular** iff $\mathrm{pop}(v) > \frac{\mathrm{deg(v)}}2$: i.e. *the vertex has higher degree than most of its neighbors*. **Are there any graphs where more than half of the vertices are popular?** Note that the counterexamples given in [Average degree of neighbors in a simple graph (-> Friendship paradox)](https://mathoverflow.net/questions/205848/average-degree-of-neighbors-in-a-simple-graph-friendship-paradox) do not work here.



Degree of neighbors in a simple graph (friendship paradox variant)
Well, a modification of the previous example works. Take some number $n$ such that there are proper divisors $a\mid n$ and $b\mid n+1$ with $a>b$. Let $V=V\_1\sqcup V\_2$, with $|V\_1|=n$, $|V\_2|=n+1$. Take $n/a$ disjoint copies of $K\_a$ on $V\_1$, and $(n+1)/b$ disjoint copies of $K\_b$ on $V\_2$. Finally, take the *antigraph* of the union of these cliques.


Then each $v\in V\_2$ has degree $2n+1-b$; it has $n+1-b$ neighbors of the same degree, and $n>n+1-b$ neighbors of degree $2n+1-a<2n+1-b$, so $v$ is popular.


A similar method works if we need $\mathop{\rm pop}(v)>(1-\epsilon)\deg(v)$ for at least half of the vertices. 


