2
$\begingroup$

$G$ be a graph with $v$ vertices and $e$ edges.Let $M$ be maximum degree of the vertices of $G$, and let $m$ be the minimum degree of the vertices $G$.Show that $$m \le 2e/v \le M$$

I am completely stuck on this problem .please help me.

$\endgroup$

1 Answer 1

3
$\begingroup$

Let $V$ be the set of vertices. We have, $mv \leq \sum_{u\in V} deg(u) \leq Mv$, since $m \leq deg(u) \leq M$ for all $u$ . But $\sum_{u\in V} deg(u) = 2e$. Therefore, $mv \leq 2e \leq Mv$ and thus $m \leq \frac{2e}{v} \leq M$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .