What is the maximum number of edges in an acyclic undirected graph with n vertices? A. n - 1 B. n C. n + 1 D. 2n - 1

GATE 2004 · Discrete Mathematics · Graph Connectivity · medium

Answer: n - 1

1. Apply the forest edge formula: A forest with n vertices and k components has n - k edges. Setting k = 1 (one connected component = a spanning tree) gives edges = n - 1.
2. Confirm n - 1 is the strict upper bound: Adding any additional edge to a spanning tree creates a cycle, so n - 1 is the strict maximum for any acyclic graph.