What is the maximum number of edges in an acyclic undirected graph with n…
2004
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
Attempted by 377 students.
Show answer & explanation
Correct answer: A
Answer: n-1
Explanation: An acyclic undirected graph is a forest, i.e., a collection of trees.
Each tree with k vertices has exactly k-1 edges.
If the forest has components with sizes k1, k2, ..., kr (sum ki = n), the total number of edges is (k1-1)+(k2-1)+...+(kr-1) = n - r, where r is the number of components.
To maximize the number of edges, minimize the number of components r. The smallest possible r is 1 (a single connected component), giving n-1 edges.
Adding any additional edge to a tree creates a cycle, so n-1 is the largest number of edges an acyclic undirected graph on n vertices can have.
Example: For n = 4, a tree has 3 edges. Any 4th edge would form a cycle, so the maximum without cycles is 3 = 4-1.