Adobe Interview Question
Software Development ManagersCountry: 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