GESP 七级 · GESP 202403 C++ 七级 第 4 题

一个连通的简单无向图，共有 $28$ 条边，则该图至少有（ ）个顶点。

图的存储方式：邻接矩阵（O(n²)空间，适合稠密图）、邻接表（O(n+m)空间，适合稀疏图）。

有向完全图边数为n(n-1)，无向完全图边数为n(n-1)/2。简单图不含自环和重边。

【考点】图的边数与顶点数关系｜完全图｜连通图性质

解题思维：先由简单图边数上限公式 n(n-1)/2≥28，解得最小整数n=8。再验证连通性——K₈恰好28条边且天然连通，故8个顶点即可构出满足条件的图。通法：给定边数E，求最小顶点数n满足n(n-1)/2≥E，取上取整。

陷阱拆解：错误选项B源于误用n(n-1)计算（未除2）；选项A/D是未考虑完全图极限情况。最阴险处在于"连通"二字——若只背"简单图最大边数"公式，可能忽略连通性要求，但本题中K₈同时满足连通与边数约束，故陷阱实为"是否意识到完全图即为连通图"。此外，若误以为"边越多顶点越多"，会选D，但实际边数增长是二次的，顶点数只需线性增长。

反命题思维：若将"简单图"改为"允许重边"，则n可更小（如n=8时仍为28，但n=7时重边可达28）；若加"无环"条件，则需考虑树结构，答案将完全不同。刷到此类题，先问：命题人是否在考极端构造还是常规计数？