Question

What is the relationship between the sum of the degreesof the vertices in an undirected graph and the number ofedges in this graph? Explain why this relationship holds.

Short answer

\[2m = \sum\limits_{v \in V} {\deg (v)} \]

Hence, the sum of the degrees must be even, since m is an integer.

Step-by-step solution

Step 1: Explanation

Given m is the number of edges of an undirected graph and V is the set of vertices then

\[2m = \sum\limits_{v \in V} {\deg (v)} \]

To prove this relationship we may simply consider each vertex and sum their degrees.

However, since every edge connects two vertices together, the total number of edges must be precisely half this value. And so,

\[m = \frac{1}{2}\sum\limits_{v \in V} {\deg (v) \Rightarrow 2m = \sum\limits_{v \in V} {\deg (v)} } \]