The number of edges in a regular graph of degree d and n vertices is ____________.

GATE 1994 · Discrete Mathematics · Graph Connectivity · medium

Answer: The number of edges in a d-regular graph on n vertices is nd/2.

1. Compute total degree sum: Each of n vertices has degree d. Total degree sum = n * d. By the handshaking lemma: nd = 2|E|.
2. Solve for the number of edges: |E| = nd/2. Verification: Petersen graph (n=10, d=3): |E| = 30/2 = 15. K_4 (n=4, d=3): |E| = 12/2 = 6 = C(4,2). Both confirmed.