Dark Mode

211 views

0 votes

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**