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

Question

我们知道:

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

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

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

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

Answer 1

Can we prove or disprove that if there's an undirected connected graph with more than N-1 edges, it must contain one of the graphs in M?

假设多于N-1条边的无向连通图g有N个顶点，答案是"is"。

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