第 7 题
若 G 是一个具有 36 条边的非连通无向简单图，则图 G 的结点数至少是（ ）。
A. 11 B. 10 C. 9 D. 8
[tag_link]
正确答案：B
首先，由于 G 是非连通无向简单图，它至少包含两个连通分支。 设结点总数为 n，边数为 36。 为了最小化 n，应使一个连通分支尽可能大（边数多），而其他分支尽可能小（如孤立点，不贡献边数）。 因此，考虑图由一个具有 m 个结点的连通分支和若干孤立点组成，其中所有边均来自该连通分支，即该分支有 36 条边。
对于 m 个结点的简单连通图，边数最多为 m(m-1)/2，因此需满足 m(m-1)/2 ≥ 36。 计算得 m(m-1) ≥ 72。 当 m=9 时，9×8=72，即完全图 K9 恰有 36 条边。 此时若图仅含 K9，则为连通图，但要求非连通，故需至少增加一个孤立点，使结点数 n ≥ m+1=10。 因此 n=10 是可能的构造：一个 9 结点的完全图（36 条边）和一个孤立点，图是非连通的，总边数 36。
验证更小的 n：若 n=9，则非连通图的最大边数出现在两个分支分别为 8 和 1 个结点时，最大边数为 8×7/2+0=28<36，无法达到 36 条边。 n=8 时更不可能。 因此，满足条件的结点数至少为 10。