2
$\begingroup$

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 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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Or take a union of lots and lots of copies of an n-regular graph, and a single m-regular graph, where m<n. As you take more and more copies of the n-regular graph, the vertices of above-average degree n are a larger and larger proportion of all the vertices. $\endgroup$
    – James Cranch
    Commented May 6, 2015 at 9:03

You must log in to answer this question.