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


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}$.

  • $\begingroup$ Thanks for the answer, but I need graph to be connected. $\endgroup$ – aaa Aug 23 '17 at 6:38
  • $\begingroup$ @aaa: The connected case is still not much different. See update. $\endgroup$ – Max Alekseyev Aug 23 '17 at 8:51

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.