algorithm - 具有超过 N-1 条边的连通图是否总是包含具有 N-1 条边的连通图？

Question

我们知道：

如果我们有 N 个顶点要构建一个连通的无向图，您至少需要 N-1 条边。令 M 为具有 N-1 条边的可能连通无向图的集合。

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

我们能否证明或反证，如果有一个具有 N-1 条以上边的无向连通图，它必须包含 M 中的一个图？换句话说，我们可以取 M 中的一个图并添加边来创建这个新图吗？

（通过“包含”，我的意思是它具有另一个图的所有边缘以及更多边缘。）

Answer 1

我们能否证明或反证，如果有一个具有 N-1 条以上边的无向连通图，它必须包含 M 中的一个图？

假设具有 N-1 条以上边的无向连通图 g 有 N 个顶点，答案是“是”。

您可以通过构造一个g 的生成树来证明这一点，它是一个具有 N 个顶点和 N-1 条边的子图。问题说明 M 包含所有此类图，g 的生成树是 M 的成员。由于生成树是通过从 g 中删除边来构造的，因此您可以将这些边添加回来，从而从 M 的成员返回到原始图 g.

Answer 2

不，不一定是这样。例如，想象一个有 2n 个节点（因此有 2n - 1 条边）的路径图。剪掉中间边缘，将图分成两个连接的组件，每个组件都是路径图。这两条路径都有 n - 1 条边，但两个连通分量都不是具有 2n - 2 条边的连通图。