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

A. 6 B. 15 C. 16 D. 21

[tag_link]

正确答案：C

结论

至少需要 16 条边，选项 C 正确。

推导

要让 7 个顶点仍然不连通，边数最多的构造是一个含 6 个顶点的完全图 (K_6) 加 1 个孤立顶点，最多有 (\binom{6}{2}=15) 条边。因此再增加 1 条边后，不可能保持不连通，保证连通所需的最少边数为

[ \binom{7-1}{2}+1=\binom{6}{2}+1=16。 ]

一般地，7 个顶点的无向图有至少 (\binom{n-1}{2}+1) 条边时必连通。

易错点

不要把连通图的下界 (n-1=6) 当成“无论如何都连通”的保证值；6 条边可以只组成一棵树，也可以分散在多个连通分量中。保证值要从“最密的不连通构造”出发计算。