请求证明：顶点数≥2的简单连通图存在可移除顶点得连通子图

方法一：最长路径端点法 #

• 在图中取一条最长路径（包含顶点数量最多的路径），设其两个端点为u和v。
• 我们证明：移除端点u后，子图一定连通。
• 假设移除u后子图不连通，那么原图中存在两个顶点a、b，移除u后a和b分属不同连通分支。由于原图连通，a到b的所有路径都必须经过u。
• 但u是最长路径的端点，它的所有邻接点都在这条最长路径上——否则我们可以把u的这个非路径邻接点加到路径里，得到更长的路径，和“最长路径”的定义矛盾。
• 这时候a、b中至少有一个不在最长路径上，不妨设a不在。那么从a到u的路径加上原最长路径，会形成一条更长的路径，这又和最长路径的定义矛盾。因此假设不成立，移除u后的子图必然连通。

方法二：数学归纳法 #

• 基例验证：当顶点数n=2时，两个顶点通过一条边连通。移除任意一个顶点后，剩下单个孤立顶点（单个顶点的图视为连通），结论成立。
• 归纳假设：假设所有顶点数k满足2≤k≤n的简单连通图，都存在这样的可移除顶点。
• 归纳推导：考虑有n+1个顶点的简单连通图G：
  • 如果G是树（无环连通图），树中必然存在度数为1的叶子节点。移除任意叶子节点后，剩下的子图仍是树（连通无环），满足条件。
  • 如果G不是树，那么G中存在至少一个环。任取环上一个顶点x，移除x后子图仍连通：环上其他顶点可通过环的剩余部分保持连通，非环顶点到环的路径也不会因x被移除而中断（可走环的另一侧）。因此结论对n+1个顶点的图也成立。

补充说明 #

你提到的例子中存在不能移除的顶点（比如割点E），但结论只要求图中至少存在一个可移除顶点，而非所有顶点都满足条件，这和我们的证明结果完全一致。

内容的提问来源于stack exchange，提问作者Ftyupl