NOIP 提高 2014 第一轮 第 13 题：设G是有6个结点的完全图，要得到一棵生成树，需要从G中删去（）条边。

题目

设 $G$ 是有 $6$ 个结点的完全图，要得到一颗生成树，需要从 $G$ 中删去(  )条边.

选项

• A. 6
• B. 9
• C. 10
• D. 15

答案

C

题解

考点定位

本题考「完全图生成树」,对应大纲 3.3.1 生成树（难度【2】）。

解题过程

K₆ 边数 C(6,2)=15；生成树保留 5 条边 ⇒ 删 15−5=10 条。

选 C。

易错提醒

① 生成树 = n−1 条边；② 任意连通图的生成树边数恒为 n−1。