Tight upper bound on the number of high degree vertices

Question

Let $G$ be a undirected graph with $n$ many vertices and $m$ many edges. Let us define $q = \Theta \big(\frac{n} {\log n}\big)$, now let us call a vertex $v$ big if degree$(v_i) \ge \frac{m}{q}$.

Question : How many big vertices will be there in a graph ?

I know the loose upper bound is $q$, Is it tight ? Is there a known tight upper bound?

Thank you

Answer 1

Suppose there are $b$ big vertices. Then there are at least $\frac{mb}{2q}$ edges incident to these vertices. Hence, $$\frac{mb}{2q} \leq m$$ implying that $b\leq 2q$.

To get an example with $2q$ big vertices, let them form an $\frac{m}{q}$-regular graph and the other $n-2q$ vertices be isolated.

---

UPDATE. For a connected graph, we similarly have $$\frac{\frac{m}{q}b + (n-b)}2 \leq m$$ implying that $$b\leq \frac{2m-n}{m-q}q = \left(2-\frac{n-2q}{m-q}\right)q.$$ This upper bound is $2q - O(1)$ when $m=\Omega(\frac{n^2}{\log n})$.

To get a graph with $b=\frac{2m-n}{m-q}q$, first form a bipartite graph with parts $B$ and $N$ of size $b$ and $n-b=\frac{m(n-2q)}{m-q}$, respectively, where each vertex of $B$ has degree $\frac{n-b}{b}=\frac{n-2q}{2m-n}\frac{m}{q}$ and each vertex of $N$ has degree $1$. Then add a connected regular graph on $B$, where each vertex has degree $\frac{m}{q}-\frac{n-b}{b} = \frac{2(m-n+q)}{2m-n}\frac{m}{q}$.