NOIP 普及 2013 第一轮 第 10 题：使无向图不连通至少需要删除的边数

题目

在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有 $4$ 个顶点、$6$ 条边的连通图。若要使它不再是连通图，至少要删去其中的（	）条边。

选项

• A. 1
• B. 2
• C. 3
• D. 4

答案

C

题解

考点定位

本题考「连通性与割边」,对应大纲 3.3.1 连通图（难度【3】）。

解题过程

4 点 6 边连通图 = K₄（完全图）。K₄ 边连通度 = 3（每点度数 3）⇒ 至少删 3 条边才不连通。

选 C。

易错提醒

① 完全图 Kₙ 的边连通度 = n−1；② 判定：孤立一个点需删去它关联的所有边。