🏷️ 知识点：边数与顶点数

一个有 n 个顶点和 n 条边的无向图一定是（ ）。

A. 连通的 B. 不连通的 C. 无环的 D. 有环的

[tag_link]

正确答案：D

结论

该图一定有环。

推导

无向森林若有 n 个顶点，边数至多为 n−1；当边数达到 n 时，不可能仍为森林，必含至少一个环。

易错点

n 条边不能推出连通；图可以分成多个连通分量，但边数超过森林上限仍必有环。

对于无向图 (G=(V,E))，下列选项中，正确的是（ ）。

A. 当 (|V|>|E|) 时，(G) 一定是连通的 B. 当 (|V|<|E|) 时，(G) 一定是连通的 C. 当 (|V|=|E|+1) 时，(G) 一定是不连通的 D. 当 (|V|>|E|+1) 时，(G) 一定是不连通的

[tag_link]

正确答案：D

结论

选项 D 正确：若 (|V|>|E|+1)，则 (|E|<|V|-1)，图不可能连通。

推导

含 (|V|) 个顶点的连通无向图至少需要 (|V|-1) 条边，等号情形就是生成树。D 的条件等价于 (|E|<|V|-1)，违反连通图的必要条件，因此必不连通。

A、B 都不是充分条件：顶点数大于边数时可以有多个孤立顶点；边数大于顶点数时也可以是一个稠密连通分量加孤立顶点。C 也错误，因为 (|E|=|V|-1) 的树就是连通图。

易错点

要区分“连通的必要条件”和“充分条件”。(|E|\ge |V|-1) 只是连通所需的必要条件，不足以保证连通；只有 (|E|<|V|-1) 才能直接推出一定不连通。

若无向图 (G=(V,E)) 含有 7 个顶点，要保证图 (G) 在任何情况下都是连通的，则需要的边数最少是（ ）。

A. 6 B. 15 C. 16 D. 21

[tag_link]

正确答案：C

结论

至少需要 16 条边，选项 C 正确。

推导

要让 7 个顶点仍然不连通，边数最多的构造是一个含 6 个顶点的完全图 (K_6) 加 1 个孤立顶点，最多有 (\binom{6}{2}=15) 条边。因此再增加 1 条边后，不可能保持不连通，保证连通所需的最少边数为

[ \binom{7-1}{2}+1=\binom{6}{2}+1=16。 ]

一般地，7 个顶点的无向图有至少 (\binom{n-1}{2}+1) 条边时必连通。

易错点

不要把连通图的下界 (n-1=6) 当成“无论如何都连通”的保证值；6 条边可以只组成一棵树，也可以分散在多个连通分量中。保证值要从“最密的不连通构造”出发计算。

已知无向图 (G) 含有 16 条边，其中度为 4 的顶点个数为 3，度为 3 的顶点个数为 4，其余顶点的度均小于 3。图 (G) 所含的顶点个数至少是（ ）。

A. 10 B. 11 C. 13 D. 15

[tag_link]

正确答案：B

结论

图 (G) 至少含有 11 个顶点，选项 B 正确。

推导

握手定理给出所有顶点度数之和 (2|E|=2\times16=32)。已知度为 4 和度为 3 的顶点贡献

[ 3\times4+4\times3=24。 ]

剩余顶点的度小于 3，且为了让顶点数尽可能少，应让它们尽量取最大的允许度数 2。设这样的顶点有 (x) 个，则 (24+2x=32)，解得 (x=4)。所以顶点总数至少为 (3+4+4=11)。

易错点

“度小于 3”意味着最大只能取 2，不能把余下度数 8 用 3 个顶点平均分摊；那会使每个顶点的度达到 (8/3)，且有顶点度为 3，违反条件。先用握手定理算余量，再用最大允许度数求最少顶点数。