Graph theory , poset question

[mahjk17]

"If G = (V,E) where V = n vertices and E = m edges, show that the minimum and maximum degree is at most (2m)/n. " I am having trouble with this problem. My attempt: I know that the number of edges of a graph is equal to half the amount of degrees. But I don't know where n vertices comes into factor?

 

[pka]

"If G = (V,E) where V = n vertices and E = m edges, show that the minimum and maximum degree is at most (2m)/n. " I am having trouble with this problem. My attempt: I know that the number of edges of a graph is equal to half the amount of degrees. But I don't know where n vertices comes into factor?

Suppose that \(\displaystyle a=\min\{\deg(v):v\in\mathcal{V}\}~\&~b=\max\{\deg(v):v\in\mathcal{V}\}\).
You say that you understand that \(\displaystyle \sum\limits_{v \in V}^{} {\deg (v)} = 2\left| E \right| = 2m\)

So \(\displaystyle a \leqslant \dfrac{2|\mathcal{E}|}{|\mathcal{V}|} \leqslant b\)

 

[mahjk17]

Thanks pka!! But I am still a bit confused because on how you got 2E = 2m. Shouldn't it be 2/E = m/2 since the degree total of a graph G is twice as much as the edges contained in that graph so that will make the edges half the amount of degrees?

 

[pka]

Thanks pka!! But I am still a bit confused because on how you got 2E = 2m. Shouldn't it be 2/E = m/2 since the degree total of a graph G is twice as much as the edges contained in that graph so that will make the edges half the amount of degrees?

You said that you understand \(\displaystyle \sum\limits_{v \in V}^{} {\deg (v)} = 2\left| E \right|\). Do you?
Well \(\displaystyle \left| E \right| =m\) so \(\displaystyle 2\left| E \right| = 2m\).

Now \(\displaystyle a|V|\le\sum\limits_{v \in V}^{} {\deg (v)}\le b|V| \)

So we get \(\displaystyle a\le\frac{2|E|}{|V|}\le b\) OR \(\displaystyle a\le\frac{2m}{n}\le b\)

 

[mahjk17]

Ohhh.. I probably had a brain freeze when I first looked at it. I understand now, thank you very much!