How Does Vertex Degree Range Affect Edge Count in a Graph?

[SpatialVacancy]

Help me with a proof!

Suppose that G is a graph with v vertices and e edges and that the degree of each vertex is at least d_{min} and at most d_{max}. Show that:

\dfrac{1}{2}d_{min}\ \cdot\ v \ \leq \ e \ \leq \ \dfrac{1}{2}d_{max}\ \cdot\ v
​

I don't have an idea of where to start on this problem. Thank you for your help!

 

[HallsofIvy]

Every edge connects 2 vertices. Suppose every edge had degree exactly d_min. How many edges would there be?

 

[thepatientmental]

Sure, I'd be happy to help you with this proof! Let's start by defining some terms to make things clearer. The degree of a vertex in a graph is the number of edges that are incident to that vertex. So for this problem, we have a graph G with v vertices and e edges, and the degree of each vertex is at least d_{min} and at most d_{max}.

To prove this statement, we will use the Handshaking Lemma, which states that the sum of the degrees of all vertices in a graph is equal to twice the number of edges. In other words,

\sum_{v \in V} deg(v) = 2e

where V is the set of all vertices in the graph.

Now, let's consider the minimum and maximum degrees of the vertices in G. We know that the degree of each vertex is at least d_{min} and at most d_{max}, so we can write the following inequalities:

d_{min} \leq deg(v) \leq d_{max}

for all vertices v in G. Multiplying both sides by v and summing over all vertices in G, we get:

\sum_{v \in V} d_{min} \leq \sum_{v \in V} deg(v) \leq \sum_{v \in V} d_{max}

Using the Handshaking Lemma, we can rewrite the left and right sides as:

d_{min}v \leq 2e \leq d_{max}v

Finally, dividing both sides by 2, we get the desired result:

\dfrac{1}{2}d_{min}\ \cdot\ v \ \leq \ e \ \leq \ \dfrac{1}{2}d_{max}\ \cdot\ v

Therefore, we have proven that the number of edges e in G must be between \dfrac{1}{2}d_{min}\ \cdot\ v and \dfrac{1}{2}d_{max}\ \cdot\ v, as desired. I hope this helps! Let me know if you have any other questions or if you need further clarification.