1
$\begingroup$

I don't know how to proceed for this problem. I would appreciate any help. Thanks!

Let $\delta$ and $\Delta$ be the minimum and maximum degree of the vertices of an undirected graph G.

Show that $\delta \leq \frac{2\left | E(G) \right |}{\left | V(G) \right |}\leq \Delta $.

2 Answers 2

6

HINT: Use the basic fact relating degrees of vertices to number of edges: $\sum_{v\in V(G)}\deg v=2|E(G)|\;.$ What are the minimum and maximum possible values of the sum?

-1

Let $e$ be the no. of edges. Let $v$ be the no. of vertices. Let $mn$ be min degree of vertex in graph. Let $mx$ be the max degree of vertex in graph. every vertex's degree must lie between this min and max limit $\min\leq \deg(v)\leq \max$ $\min\leq 2e\leq \max$ // using the above hint thus for n vertices in a graph, $n(\min)\leq 2e\leq n(\max)$ and so $\min \leq 2\frac{e}{n}\leq \max$

  • 0
    welcome to [MATHEMATICS](http://math.stackexchange.com/). You can use [this link](http://meta.math.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference) for more information too.2014-02-23