题目

若无向图 G=(V,E) 中含有 7 个顶点，要保证图 G 在任何情况下都是连通的，则需要的边数最少是()。

错因

A

混淆了"一棵生成树"与"任意情况下保证连通"。7 个顶点的生成树只需 6 条边，但那是某一特定连接方式下连通；题目问的是无论边怎么分布，图都必然连通，6 条边做不到这一点（6 条边全给 6 个顶点连成环，第 7 个顶点孤立即不连通）。

B

误算为保证连通所需的最少边数。15 条边时，仍然存在不连通的情况：把 1 个顶点孤立，其余 6 个顶点构成完全图，边数恰好 = C(6,2) = 15，此时图不连通。因此 15 条边尚不能保证连通，还需多加 1 条。

D

误以为需要 7 个顶点的完全图才能保证连通。C(7,2)=21 条边是完全图的边数，远超"保证连通"的最低要求。

总解析

等价转化：n 个顶点的无向图，加多少条边才能保证图在任何情况下连通？

等价于：不连通图最多能有多少条边？答案加 1 就是所求。

最坏不连通情况：让 1 个顶点孤立，其余 n-1 个顶点组成完全子图——这样边数最多但仍不连通。

• n=7 时，6 个顶点的完全图边数 = C(6,2) = 15，加上孤立顶点后图不连通。
• 只要再加 1 条边（必然连接那个孤立顶点），图就连通了。

所以最少需要 15 + 1 = 16 条边，才能保证 7 个顶点的无向图在任何情况下都是连通的。

最终答案是 C（16）。