Be the first user to complete this post

Add to List 
Maximum number edges to make Acyclic Undirected/Directed Graph
Given Given V vertices, what is the maximum number of edges can be added to make Acyclic Undirected Graph. Follow up  what is the maximum number of edges that can be added to make Acyclic Directed Graph.
Example:
Approach:
For Undirected Graph  It will be a spanning tree (read about spanning tree) where all the nodes are connected with no cycles and adding one more edge will form a cycle. In the spanning tree, there are V1 edges.
For Directed Graph  Construct the graph similar to topological order (Read about topological order  where all the edges go to one direction and there will not be any circular dependency, means there is no cycle). Take the first vertex and have a directed edge to all the other vertices, so V1 edges, second vertex to have a directed edge to rest of the vertices so V2 edges, third vertex to have a directed edge to rest of the vertices so V3 edges, and so on. This will construct a graph where all the edges in one direction and adding one more edge will produce a cycle.
So the total number of edges = (V1) + (V2) + (V3) ++2+1 = V(V1)/2. (sum of first N natural numbers is N(N+1)/2)
Complete Code:
Output:
Maximum edges to make Acyclic Undirected Graph with 3 vertices are: 2 Maximum edges to make Acyclic Directed Graph with 3 vertices are: 3  Maximum edges to make Acyclic Undirected Graph with 4 vertices are: 3 Maximum edges to make Acyclic Directed Graph with 4 vertices are: 6  Maximum edges to make Acyclic Undirected Graph with 5 vertices are: 4 Maximum edges to make Acyclic Directed Graph with 5 vertices are: 10
Also Read: