Question

If a graph G has 10 vertices and each vertex has degree 3, how many edges does G have?

• A. 30
• B. 15
• C. 10
• D. 20

Hint:

Because the sum of degrees is always $2E$, the sum must always be an even number. This implies that any graph must contain an even number of vertices that have an odd degree.

Answer 1

The Correct Option is B

Concept: This problem is solved using the Handshaking Lemma (also known as the Degree Sum Formula).
• Theorem: In any undirected graph, the sum of the degrees of all vertices is equal to twice the number of edges.
• Formula: $\sum_{i=1}^{n} \text{deg}(v_i) = 2|E|$

Step 1: Calculating the total sum of degrees.
The graph has 10 vertices ($n = 10$). Each vertex has a degree of 3. \[ \text{Total Sum of Degrees} = \text{Number of vertices} \times \text{Degree per vertex} \] \[ \text{Total Sum} = 10 \times 3 = 30 \]

Step 2: Applying the Handshaking Lemma.
According to the lemma, $2 \times (\text{Number of edges}) = 30$. Let $E$ be the number of edges: \[ 2E = 30 \]

Step 3: Solving for E.
Divide both sides by 2: \[ E = \frac{30}{2} = 15 \] The graph has 15 edges.