Degree of neighbors in a simple graph (friendship paradox variant)

Question

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).

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) do not work here.

Answer 1

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.