Menu
There are 'n' vertices and 0 edges of an undirected graph. What can be the maximum number of edges that we can draw such that the graph remains disconnected.
I have made the solution that we can exclude one vertex and can find the maximum number of edges between n-1 vertices of undirected graph, so that the graph still remains disconnected.
which is n(n-1)/2 for n vertices and will be (n-1)(n-2)/2 for n-1 vertices. Can there be a better solution?
292
What is the maximum number of edges in a bipartite graph having 10 vertices? Explanation: Let one set have n vertices another set would contain 10-n vertices. Total number of edges would be n*(10-n), differentiating with respect to n, would yield the answer. 11.
Therefore a simple graph with 8 vertices can have a maximum of 28 edges.
Number of edges in a complete bipartite graph is a*b, where a and b are no. of vertices on each side. This quantity is maximum when a = b i.e. when there are 7 vertices on each side. So answer is 7 * 7 = 49.
You can resolve this using analysis. Take your idea and generalize it. You divide the n vertices in two groups , of size x and n-x.
Now the number of edges is a function of x, expressed by
f(x)= x(x-1)/2 + (n-x)(n-x-1)/2
f(x) = 1/2(2x^2 - 2nx +n^2 - n)
The value which maximize this function is the partition size you want. If you make calculation you find that it decrease from x=0 to x=n/2, then increase to x=n. As x = 0 or x = n means the graph is collected, you take the next greatest value which is x=1. So your intuition is optimal.
59
Your solution should be the best solution.
Because any new edge added must have the nth vertex at one end.
41
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
