Dowód nierówności w grafie

[Fray]

Witam.

Dla grafu \(\displaystyle{ G = (V,E)}\) mam udowodnić taką nierówność:
\(\displaystyle{ \delta(G) \le \frac{2|E|}{|V|} \le \Delta(G)}\)

Nie wiem jak to ugryźć. Rozrysowałem sobie kilka grafów i poza tym, że to faktycznie prawda nie doszedłem do niczego sensownego.

Prosiłbym o pomoc.

[Qń]

Wskazówka - użyj lematu o uściskach dłoni:
\(\displaystyle{ 2|E|= \sum_{v\in V} deg (v)}\)
i wykorzystaj szacowanie \(\displaystyle{ \delta (E) \le deg (v)\le \Delta (E)}\) (prawdziwe dla dowolnego wierzchołka).

Q.

[Fray]

Myślę, że chodzi tu o to, że:
1. \(\displaystyle{ \frac{2|E|}{|V|}}\) to tak jakby średnia arytmetyczna stopni wszystkich wierzchołków
2. Jeżeli wzięlibyśmy zbiór stopni wierzchołków to średnia arytmetyczna jego elementów będzie większa równa od elementu minimalnego i mniejsza równa od elementu maksymalnego.

Dziękuję. Czy miałbyś jakąś wskazówkę co do zapisania tego bardziej formalnie?

[Qń]

Ale co jest niejasnego w podanej wskazówce? Nie wiesz jak wykorzystać szacowanie:
\(\displaystyle{ \delta (E) \le deg (v)\le \Delta (E)}\)
?
Wystarczy zsumować stronami takie nierówności dla wszystkich \(\displaystyle{ v\in V}\):
\(\displaystyle{ \sum_{v\in V}\delta (E) \le \sum_{v\in V}deg (v)\le \sum_{v\in V}\Delta (E)}\)

Q.

[Fray]

Łał. No pewnie. Teraz to prościzna. Na siłę próbowałem skomplikować.

Dziękuję