CSP-S 2019 第一轮 第8题：G是一个非连通无向图（没有重边和自环），共有28条边，则该图至少有

题目

$G$ 是一个非连通无向图（没有重边和自环），共有 $28$ 条边，则该图至少有 （）个顶点。

选项

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

答案

B

题解

答案是 B. 9。

因为没有重边和自环，\(8\) 个顶点最多有 \[ \binom{8}{2}=\frac{8\times7}{2}=28 \] 条边。但要达到 \(28\) 条边，任意两个顶点之间都必须有边，即构成完全图 \(K_8\)，它是连通图，不符合题意。因此至少需要 \(9\) 个顶点。

而 \(9\) 个顶点确实能满足：让其中 \(8\) 个顶点构成完全图，再加上 1 个孤立顶点。此时恰有 \(28\) 条边，且图不连通。

所以最少有 \(\boxed{9}\) 个顶点。