CSP-S 2021 第一轮 第7题：G是一个非连通简单无向图（没有自环和重边)，共有 36条边，则该图至少有（）个点

题目

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

选项

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

答案

C

题解

选 C．10。

简单无向图有 \(n\) 个点时，最多有 \(\frac{n(n-1)}2\) 条边。

• 8 个点及以下：最多有 \(\frac{8\times7}{2}=28\) 条边，不够 36 条。
• 9 个点：最多恰好有 \(\frac{9\times8}{2}=36\) 条边。但要达到 36 条边，每两个点之间都必须有边，即完全图，它是连通的，不符合题意。
• 10 个点：取一个有 9 个点的完全图，再加一个孤立点。边数仍为 36，且图非连通，符合题意。

所以至少需要 10 个点。