The minimum number of edges in a connected cyclic graph on n vertices is: A. n - 1 B. n C. n + 1 D. None of the above

GATE 1995 · Discrete Mathematics · Graph Connectivity · easy

Answer: Minimum number of edges = n => option B

1. Connected lower bound: Any connected graph on n vertices must have at least n - 1 edges; equality holds exactly for trees. So we cannot use fewer than n - 1 edges and stay connected.
2. A tree has no cycle: With exactly n - 1 edges the connected graph is a tree, which by definition contains no cycle. Hence n - 1 edges cannot satisfy the 'cyclic' requirement, ruling out option A.
3. Add one edge to get a cycle: Adding a single extra edge to a tree creates exactly one cycle while keeping the graph connected, giving n edges. A single cycle through all n vertices realises this with n edges, so n edges are achievable and necessary. The minimum is n, which is option B.