CareerCup

Acyclic undirected graph:

V-1 edges. Spanning tree of the graph.


Acyclic directed graph:

Imagine the graph topologically sorted. It can only have edges going down (from top to bottom), otherwise it would have cycles.

The way to maximize the number of edges without creating cycles is to connect a given vertex to all other vertices that are below it (again, imagining the graph in a topological order). For instance, the vertex 0 is connected to 1, 2, 3, ..., V-1; vertex 1 to 2, 3, ..., V-1. So on and so forth.

Therefore, the total number of edges is: Sum (i=0 to V-1) i, which is equal to (V^2-V)/2.

For directed/undirected acyclic graph: nC2 - 1 (because there is only 1 cyclic graph possible)

(V^2 - V)/2 is the maximum number. Let's prove it.

Let G(V, E) be an acyclic graph with the most number of edges. Then:

Claim: There is a (the) sink node with exactly V - 1 incoming edges where a sink node is a vertex with no outgoing edges.

Proof: First note that we have to have a sink node. Otherwise, any vertex will have at least 1 outgoing edge and hence, a cycle.

Now note that for the optimal graph, the sink node must have "V - 1" incoming edges. Simply if it does not, then you can add the missing edges to the sink node and still produce no cycles. Therefore, the graph could not have possibly been optimal.

Therefore, the sink node has "V - 1" incoming edges.

Now the rest is easy. Remove this sink node from this graph and all the edges connected to it. You will get another G(V - 1, E) which is optimal. By recusing, we can go all the way to the graph with one vertex and 0 edges. This way, we are removing
(V - 1), (V - 2), ..., (1) edges to get to that graph. Therefore, the total number of edges is at most (V^2 - V) / 2.

On the other hand, as suggested above, you can indeed construct a graph with this many edges. Add an edge from vertex "0" to all other vertices except itself. Then from vertex "1" to all vertices except {0, 1}. Iterate until exactly "(V^2 - V) / 2" edges are added.