## Adobe Interview Question

Software Development Managers**Country:**India

**Interview Type:**Written Test

@Bazinga, Anonymous: No, the answer is (n-1)*(n-2)/2.

I challenge you to draw a disconnected undirected graph with no duplicate edges and no self loops that has n*(n-1)*(n-2)/2 edges like you said.

Yes right, my Bad.

We have to select number of edges, not number of ways of choosing edges (which is also not correct :P ).

Answer would be (n-1)*(n-2)/2

in any simple graph having n vertex max edges can be (n)C2 now we need max edges with a disconnected graph.

let us assume there are “X” vertex in one side & (n-x) vertex on other side.

We can say that max edges in the graph would be xC2 & (n-x)C2

Total edges in graph are P = xC2+(n-x)C2 which we need to maximize.

If we solve it by max & min concept we will get x =(n/2)

Which means we should divide it in two halves.

Just exclude one vertice and then connect all the n-1 vertices, it will be (n-1)C2 i.e. (n-1)(n-2)/2.

- alexander June 25, 2012