GESP 八级 · GESP 八级样题（C++ 组） 第 19 题

连通图 $G$ 有 $n$ 个顶点 $m$ 条边，须删除 $m-n+1$ 条边后才能变成一棵生成树。（ ）

这道题考连通图变生成树删几条边。核心就是生成树边数固定为n-1，原图m条边，直接算差值m-(n-1)即可，别被代数式绕晕。

学生最容易把'连通图'和'生成树'的边数关系搞反，误以为删边数量跟图的具体结构有关，或者把m-n+1当成某种复杂公式去推导，其实它就是简单的减法。还有人会纠结'任意删'还是'特定删'，以为要保留某些边，但生成树只要包含所有点且无环，边数就定了，多出来的边删掉就行，跟删哪条无关。

1. 考点与概念

生成树是连通图的一个子图，它包含原图所有顶点，且边数恰好为n-1，同时自身无环。这是图论里的一个铁律：任何一棵树的边数都比顶点数少1。题目里说'连通图G有n个顶点m条边'，既然已经连通，那它一定存在生成树，而且生成树的边数永远是n-1，跟m没关系。

2. 命题视角

命题人把答案包装成'm-n+1'这个代数式，就是想看你有没有真正理解'生成树边数固定'这个本质。如果你只是死记硬背'生成树有n-1条边'，看到这种式子可能会犹豫：'是不是要证明？是不是有条件？'其实不需要证明，直接代入就行。连通图这个条件看似多余，实则关键——只有连通图才有生成树，不连通的话生成树不存在，题目也就没意义了。