图具有多个连通分量时的最大边数

Question

对于算法的最终审查,出现了这样一个问题：

For a Graph G with V vertices and E edges, what is the largest number of edges 
this graph can have IF there are more than one connected components within G

由于连通组件本质上是图中的一个图，这意味着子图中的所有顶点必须从较大的图中移除，同时保持内部连通性。我能理解这种直觉，但很难把它转化成一个公式。

到目前为止，我得出的结论如下：

对于连通分量n，每个图Gn具有相应的顶点集{Vn}，使得顶点集的内容在内部连接，而在外部保持不连接。

Graph G1 = {V1}
Graph G2 = {V2}
    ...
Graph Gn = {Vn}

现在，每个{Vn}最多包含V*(V-1)条边。

如何用公式表示最大边数？

Answer 1

如果它是一个多图（有自环和平行边），那么当然任何数量的边都是可能的，但我相信这是关于边被定义为无向非自反边的图。

在这种情况下，K个节点的每个分量最多可以有K*(k-1)边。由于这是二次性质的，如果你有一个巨大的分量和一个最小的分量，那么你可以得到的最大数量的边。所以只有两个元素，分别是N-1和1个元素。

这个图将有(n-1)*((n-1)-1)=(n-1)*(n-2)=(N^2-3N+2)边，我认为这是一个包含多个分量的图中最大边数的公式。