algorithm - 对于同一双连通组件中的任何顶点 A 和 B 以及边 E，是否总是可以有一条从 A 到 B 通过 E 的简单路径？

Question

在解决一些算法问题时，遇到了使用某些双连通分量属性的问题。

假设顶点 A 和 B 在同一个双连通分量中。该组件中有边 E(u, v)。那么对于任何一对 A、B、E(都在同一个 bi-comp 中)，总有一条从 A 到 B 通过 E 的简单路径是可能的吗？

我试图找到一些反例，但失败了。然后我尝试使用同一 bi-comp 中的任何一对顶点都有 2 条边不相交的路径来证明它，这也失败了。

有人可以帮我证明这一点吗？

Answer 1

双连接意味着您可以删除任何顶点 v 并且任何一对顶点将保持连接 (wikipedia)。

所以让我们假设声明是不可能的。这意味着我们有两条路径 A 到 u 和 v 到 B，它们必须共享至少一个顶点(称为 x)。但这意味着，如果我从双连通分量中删除 x，那么要么不能将 A 连接到 u，要么不能将 v 连接到 B。但是这两对都是双连通分量的一部分，所以我们有矛盾。