wiz-icon
MyQuestionIcon
MyQuestionIcon
1
You visited us 1 times! Enjoying our articles? Unlock Full Access!
Question

What is the maximum number of edges in an acyclic undirected graph with n vertices?

A
n - 1
Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses
B
n
No worries! We‘ve got your back. Try BYJU‘S free classes today!
C
n + 1
No worries! We‘ve got your back. Try BYJU‘S free classes today!
D
2n - 1
No worries! We‘ve got your back. Try BYJU‘S free classes today!
Open in App
Solution

The correct option is A n - 1
Acyclic graph are graphs which does not contain cycle.

For maximum number of edges each vertex connect to other vertex only if it does not from a cycle i.e. from a tree with n vertices, which has maximum n - 1 edges. Ex. with 4 vertices, 3 edges maximum.

flag
Suggest Corrections
thumbs-up
0
Join BYJU'S Learning Program
similar_icon
Related Videos
thumbnail
lock
Quadrilaterals and their Properties
MATHEMATICS
Watch in App
Join BYJU'S Learning Program
CrossIcon