Graph on $\mathbb{N}$ where almost every vertex is shy

Question

The following question is loosely based on the friendship paradox.

Let $G=(V,E)$ be a simple, undirected graph. For $v\in V$, we let the neighborhood of $v$ be $N(v) = \big\{w\in V:\{v,w\}\in E\big\}$ and the degree is defined by $\newcommand{\deg}{\text{deg}}\deg(v)=|N(v)|$. Moreover, for $v\in V$ we define the set of its popular neighbors by $\newcommand{\Pop}{\text{Pop}}\Pop(v) = \{p\in N(v): \deg(p)>\deg(v)\}$.

Finally, we say $v\in V$ is shy if $|\Pop(v)|>|N(v)\setminus \Pop(v)|$.

We call a set $A\subseteq\mathbb{N}$ large if $\lim\inf_{n\to\infty}\frac{|A\cap\{1,\ldots,n+1\}|}{n+1} = 1$.

Question. Is there a graph on $\mathbb{N}$ such that every vertex has finite degree, and the collection of shy vertices is large?

Answer 1

All vertices can be shy. You may add edges to your graph recursively, on $n$-th step fixing all edges from $1,2,\ldots,n$ and possibly some other (finitely many) edges, so that $1,2,\ldots,n$ already have more than a half popular neighbors. There are no problems to perform each, say, $n$-th step: you simply add many edges from $n$ and many-many edges from its new neighbors.

Answer 2

In a star graph, all but one vertex is shy, so a simple construction is to build a star graph from $\{1,\ldots,4\}$, another from $\{5,\ldots,12\}$, etc., doubling the size each time.

Answer 3

Take any locally finite countable graph with infinitely many shy vertices, e.g., the disjoint union of $\aleph_0$ copies of $K_{1,2}$. Identify the vertex set with $\mathbb N$ in such a way that the set of non-shy vertices is identified with a set of density zero.