algorithm - Vertex Biconnected 和 Edge Biconnected 的误解

Question

如果没有顶点的删除断开连接图，则连接图是顶点双连接的。如果没有边的移除使图断开连接，则连通图是边双连通的。对下列陈述分别给出证明或反例：

(a) 顶点双连通图是边双连通图。

(b) 边双连通图是顶点双连通的。

对于A）我的尝试是应该是这种情况，因为我看不到删除顶点将如何影响边缘的双向连接。

对于 B）我的尝试是否定的，因为如果我们有一个桥，连接两个图，删除该边将不再使图顶点双连接。

也许我在这里完全错了，任何帮助将不胜感激。

Answer 1

a) 的证明：反证法。令 G = (V,E) 是顶点双连通的。假设它不是边双连接的。然后存在一条边 e = {v,w}，我们可以删除这样 G' = (V, E \ {e}) 是不连通的。但是我们也可以从 G 中删除 v 或 w 并断开图（因为删除边的任一端顶点也会删除该边），这与 G 是顶点双连接的矛盾；因此 G 也必须是边双连通的。