Maximum number of edges in undirected graph with n vertices with k connected components?

Question

I couldn't answer the question myself because i don't see any similar behavior for all the examples i tried. The question again: Maximum number of edges in undirected graph with n vertices with k connected components? Thanks.

Answer 1

This answer depends on whether your graphs are allowed to have self-loops or not. For simplicity, I'm going to assume they aren't.

If you have a connected component with x nodes in it, the maximum number of edges you can have in that connected component is x(x - 1) / 2. Therefore, if you have n total nodes and k different connected components, you can imagine distributing the nodes into the connected components in a way that maximizes the sum of x(x - 1) / 2 across the connected components.

Specifically, suppose your CC's have n₁, ..., n_k nodes each. You want to solve the following quadratic program:

Maximize: n₁(n₁ - 1) / 2 + ... + n_k(n_k - 1) / 2

Subject to: n₁ + ... + n_k = n

I'm going to claim that this is maximized when k - 1 of the connected components have 1 node and the last connected component has n - k + 1 nodes in it. Intuitively, this is true because any node you remove from the huge CC will cause a large drop in the number of possible edges that will not be offset by the meager increase in the number of possible edges in the other connected component the node was added to.

Under this setup, the maximum number of possible edges in the k - 1 singleton CC's will be 0 and the maximum number of possible edges in the other CC will be (n - k + 1)(n - k) / 2. Therefore, the total should be (n - k + 1)(n - k) / 2.

Hope this helps!

Answer 2

when graph do not contain self loops and is undirected then the maximum no. of edges are-

(n-k+1)(n-k)/2

It is because maximum number of edges with n vertices is n(n-1)/2.
Now for example, if we are making an undirected graph with n=2 (4 vertices) and there are 2 connected components i.e, k=2, then first connected component contains either 3 vertices or 2 vertices, for simplicity we take 3 vertices (Because connected component containing 2 vertices each will not results in maximum number of edges). These 3 vertices must be connected so maximum number of edges between these 3 vertices are 3 i.e, (1->2->3->1) and the second connected component contains only 1 vertex which has no edge. So the maximum number of edges in this case are 3. This implies that replacing n with n-k+1 in the formula for maximum number of edges i.e, n(n-1)/2 will results in (n-k+1)(n-k)/2 which is maximum number of edges that a graph of n vertices with k connected component can have.
see image for better understanding
hope it will be helpful!!