图论最大边？

Question

如果一个简单的图有3个分量，并且这些分量有4，5，6个顶点，那么图中存在的最大边数.

(a) 26 (b) 76 (c) 30 (d) 42

如果我应用‘n个顶点和k个连通分量的图有最大边(n-k)(n-k+1)/2’的公式，为什么我会得到错误的答案？

我们不能用n作为4+5+6=15和组件数= 3吗？

Answer 1

据我所知，每个连接组件最多只能有

n*(n-1)/2

边，其中n是各连通分量的顶点数；公式是具有n顶点的完备图的边数。总之，一个人获得的最大数目为

4*3   5*4   6*5
--- + --- + --- = 6 + 10 + 15 = 31
  2     2     2

边(令人惊讶的是，这个数字没有出现在有效答案列表中)。