With V(greater than 1) vertices, how many edges at most can a Directed Acyclic Graph possess?

Category: QuestionsWith V(greater than 1) vertices, how many edges at most can a Directed Acyclic Graph possess?
Editor">Editor Staff asked 1 month ago

With V(greater than 1) vertices, how many edges at most can a Directed Acyclic Graph possess?
 
(a) (V*(V-1))/2
 
(b) (V*(V+1))/2
 
(c) (V+1)C2
 
(d) (V-1)C2
 
Enquiry is from Directed Acyclic Graph topic in division Graph of Data Structures & Algorithms I
 
The question was posed to me during an interview for a job.

1 Answers
Editor">Editor Staff answered 1 month ago

The correct answer is (a) (V*(V-1))/2
 
Easiest explanation – The first edge would have an outgoing degree of atmost V-1, the next edge would have V-2 and so on, hence V-1 + V-2…. +1 equals (V*(V-1))/2.