🏷️ 知识点：极值计数

一个有 6 个顶点的无向图，至少有（ ）条边时可以保证图是连通的。

A. 8 B. 9 C. 10 D. 11

[tag_link]

正确答案：D

结论

至少 11 条边才能保证 6 个顶点的无向图连通。

推导

不连通时，为了让边尽可能多，应取一个 5 个顶点的完全图和一个孤立点，边数为 C(5,2)=10。因此 10 条边仍可能不连通，增加一条边后必连通。一般地，n 个顶点至少需要 C(n−1,2)+1 条边保证连通。

易错点

n−1 是“构造一张连通图所需的最少边数”，不是“任意图保证连通”的阈值；保证连通要从最密的不连通图反推。