Średni stopień w grafie spójnym

[gosiak5321]

Średnim stopniem w grafie G nazywamy liczbę określoną wzorem: \(\displaystyle{ d_r{r}(G) = \frac{\left| E\right| }{\left| V\right| }}\). Wykazać, że dla grafu spójnego G zachodzi nierówność:\(\displaystyle{ 1- \frac{1}{\left| V\right| } \le d_{r}(G) \le \frac{\left| V\right| }{2}}\).

[yorgin]

Skoro graf jest spójny, to \(\displaystyle{ |V|\leq |E|+1}\) i po elementarnych przekształceniach mamy \(\displaystyle{ 1-\frac{1}{|V|}\leq d_r(G)}\).

Graf mający \(\displaystyle{ |V|}\) wierzchołków może mieć co najwyżej \(\displaystyle{ \frac{|V|^2}{2}}\) krawędzi (każdy z każdym, a że wtedy liczymy podwójnie, to dzielimy przez dwa) i to załatwia drugą nierówność.