NPTEL Assignment Question

Question

An undirected graph G has 300 edges. The degree of a vertex v, deg(v), is the number of edges connected to v. Suppose V = {v1,v2,...,v30}.

What is the value of deg(v1)+ deg(v2) + · · · + deg(v30)?

 

• A. 300
• B. 600
• C. 900
• D. None of these

Answer 1

According to Handshaking lemma,

Sum of degree of all vertices= 2*|E| 

ie, 2*total number of edges

So here, we have number of edges as 300 and we need to find sum of degrees of all vertices.

Hence. 2*300=600

Option (B)

Answer 2

Correct Answer: (B)

Let n = number of vertices in the graph and |E| = number of edges in graph.

Given |E| = 300.

By Handshaking Lemma, 

For i = 1 to n                ∑ deg(Vi) = 2 × |E|

i.e. Sum of degree of all the vertices is twice the number of Edges

Let’s understand what is the logic of above formula. Let’s consider a simple graph with only two vertices u and v and a single edge between them. The degree of vertex u = 1 and degree of vertex v = 1 and total number of edges in the graph is 1. Basically this single edge contributes degree of 1 to vertex u and degree of 1 to v. So, sum of their degrees turn out to be 2 which is equal to 2 |E|. 

We can generalize this idea and say that for any edge (u,v), this edge contributes degree 1 to both vertices of the edge (u, v). This generalization is basically Handshaking Lemma as mentioned above.

So, for the given problem, we can have

for i = 1, 2, 3, ….., 30

deg(V1) + deg(V2) + deg(V3) + ……. deg(V30) = 2 × 300 = 600

Hence answer is (B) 600