How many edges are present in a k-regular graph with n vertices?
MathWorks technical mcq question, verified with a worked answer. Free to practise - no sign-up.
How many edges are present in a $k$-regular graph with $n$ vertices?
Show answer & explanation
In a k-regular graph, every vertex has exactly degree k (connected to k other vertices). The sum of all degrees is n * k. By the Handshaking Lemma, the sum of degrees equals twice the number of edges, so edges = (n * k) / 2.
Step-by-step Derivation:
Step 1: In a k-regular graph with n vertices, each vertex has degree k.
Step 2: Sum of all vertex degrees = n * k (summing k for each of the n vertices).
Step 3: Apply the Handshaking Lemma: sum of degrees = 2 * (number of edges).
Step 4: Therefore, n * k = 2 * E, where E is the number of edges.
Step 5: Solve for E: E = (n * k) / 2.
Why other options are wrong:
- B) n * k counts degree sum, not edges (off by factor of 2).
- C) (n * (k - 1)) / 2 incorrectly uses k-1 instead of k; applies to a different graph structure.
- D) n * (k - 1) combines the errors of options B and C.