Question

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.

Answer 1

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.