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



Tight upper bound on the number of high degree vertices
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}$.


