CSP-J 2020 第一轮 第 8 题：10个顶点无向图连通所需最少边数

题目

有 $10$ 个顶点的无向图至少应该有（ ）条边才能确保是一个连通图。

选项

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

答案

A

题解

按题目的出题意图，选 A．9。

对于有 \(n\) 个顶点的无向图，要使它连通，最少需要 \(n-1\) 条边，此时这个图是一棵树。因此： \[ 10-1=9 \] 例如，把 10 个顶点排成一条链，相邻顶点之间连一条边，共 9 条边，就能连通。

但题目中“确保”的表述不够严谨：有 9 条边并不一定连通，还要看怎么连接。如果要求“无论怎么连边，都保证连通”，则需要 37 条边——因为 9 个顶点两两相连、另 1 个顶点孤立时，已有 \(\binom{9}{2}=36\) 条边，却仍不连通；这也是不连通图能有的最多边数。