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 83 students.
Show answer & explanation
Correct answer: A
An acyclic undirected graph is a forest.
The maximum number of edges occurs when the graph is connected, i.e., it becomes a tree.
A tree with n vertices has:
n−1
edges.
If one more edge is added, a cycle is formed.
Therefore, the maximum number of edges in an acyclic undirected graph with n vertices is:
n−1
A video solution is available for this question — log in and enroll to watch it.