The maximum number of edges in a n-node undirected graph without self loops is A. n^2 B. n(n-1)/2 C. n-1 D. (n+1)(n)/2

GATE 2002 · Discrete Mathematics · Graph Connectivity · easy

Answer: Maximum number of edges = n(n-1)/2, which is option B.

1. Each edge is a pair of distinct vertices: Without self loops and without multi-edges, every possible edge is determined by an unordered pair {u,v} with u != v.
2. Count the pairs with combinations: C(n,2) = n(n-1)/2, so the maximum number of edges is n(n-1)/2.