从连通图中删除一个顶点，得到连通子图

Question

我的印象是，如果我采用一个简单的连通图，那么我可以（只要它的顶点数大于或等于 2）删除一个顶点并获得一个连通的子图。

这并不适用于所有顶点，有些顶点我无法删除。 例如，

我无法在不失去连接的情况下删除 E，但我可以删除 A、B、C 或 D。

但总有一种我可以排除。你有办法证明这个结果吗？

Answer 1

设 G 为任意连通图。设 T 为 G 的任意生成树。设 v 为 T 的任意叶子。如果删除 v，则 T \ {v} 是连通的，并且是 G \ {v} 的子图，因此 G \ {v} 是连通的。

此使用的众所周知的结果：

• 每个连通图至少有 1 个生成树
• 从 n 顶点树中删除叶子会产生 (n-1) 顶点树

Answer 2

您所指的概念可能与

Articulation Point

的概念相关，也称为

Cut Vertex

。

如果连接组件中存在顶点

v

，当移除该顶点时，图形将断开连接，即分成两个或更多组件

在某些条件下，节点才有资格成为铰接点。因此，如果确定图没有这样的顶点，那么即使删除任何顶点，图仍保留为单个连通分量

请参阅此处了解更多信息