NOIP 普及组初赛 · NOIP 2013 普及组初赛试题 第 10 题

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

这题考图论里的连通性与边删减。拿到图先数顶点数和边数，判断是不是完全图，再想：让图不连通，最少要让一个顶点‘孤立’，它连出去几条边就要删几条，这就是切入点。

很多学生会只盯着‘断开两个连通块’去数边，觉得删2条就能把图分成两半，这是直觉陷阱。其实只要有一个顶点没了边，图立刻就不连通了。K4里每个顶点都连着3条边，所以必须把某个顶点的3条边全删掉，答案只能是3，不是2也不是1。

考点与概念

这道题考查的是图论中最基础的连通性概念：在一个无向图中，如果任意两点之间都存在路径，则称其为连通图。反之，只要存在至少一对点之间没有路径，图就不再连通。

题目给出的图有4个顶点、6条边。我们先判断这是什么图：4个顶点两两之间都有边，这正是完全图 K₄。在 K₄ 中，每个顶点都和其他3个顶点直接相连，所以每个顶点的度数都是3。

命题视角：为什么考这个？

命题人喜欢用这种‘看似简单实则需精确理解定义’的题目挖坑。表面上问‘至少要删几条边’，学生容易凭直觉去数‘断开成两块’需要几条边，或者觉得删一条边就能破坏连通性。但真正的关键点是：破坏连通性的最小代价，是让某个顶点彻底孤立。只要有一个顶点没有边了，它就无法到达其他任何点，连通性瞬间崩塌。