大门| 2007年大门|问题25

什么是最大整数m，使得每个具有n个顶点和n条边的简单连通图至少包含m个不同的生成树？ （A） 1. （B） 2. （C） 3. （D） N 答复: （C） 说明： 当所有节点都可以从每个节点遍历时，图是连通的。对于有n个节点的图，有n-1条最小边数。 假设有n条边，这意味着图中有一个循环。 具有这些条件的单纯形图可以是：

现在我们可以通过从循环中删除一条边，一次删除一条边，来生成不同的生成树。 最小循环长度可以是3，所以，在任何这样的图中必须至少有3个生成树。 这个问题的小测验