Sum of degrees of all nodes for a graph $G(V,E)$ can be given by..............

Question

Accepted Answer

The correct option is (2):
This is a direct application of a foundational principle in graph theory known as the Handshaking Lemma or the Degree Sum Formula. For any undirected graph $G$ with a set of vertices $V$ and a set of edges $E$, the sum of the degrees of all vertices is precisely equal to twice the number of edges, which is mathematically expressed as $\sum\_{v \in V} \text{deg}(v) = 2 \times |E|$. The conceptual reasoning behind this is that every single edge in the graph connects exactly two vertices. When we calculate the degree of a node, we count each edge incident to it. Therefore, by summing the degrees across *all* nodes, we effectively count every edge exactly twice: once for each of its two endpoints. This fundamental theorem holds true for all finite undirected graphs.

The incorrect option is (1):
Option 1, $|E|$, represents only the total number of edges in the graph. If we simply take the total count of edges, we are only counting each edge once. To correctly find the sum of degrees, we must account for the fact that each edge contributes to the degree count of two different vertices, one at each end. Therefore, $|E|$ is the total number of edges, but not the sum of their endpoints' degrees. This value would only be half of the actual sum of degrees.

The incorrect option is (3):

Option 3, $2 	imes |V|$, is twice the total number of vertices. This represents an upper bound for the sum of degrees only in specific, highly restrictive graph types, but it is not a general formula. The sum of degrees depends entirely on the arrangement and count of the edges, $|E|$, not merely the size of the vertex set, $|V|$. Therefore, for an arbitrary graph, twice the number of vertices has no general mathematical relationship to the sum of all degrees.

The incorrect option is (4):
Option 4, $|V|$, is merely the total count of vertices or nodes in the graph. The number of vertices gives us information about the size of the graph's structure but provides no information about the connectivity between those nodes. The sum of the degrees is a measure of the total connectivity (twice the edges), which is independent of just the total number of nodes. For instance, an empty graph and a highly connected graph can have the same number of vertices but drastically different sums of degrees.