具有v个节点的无向图G，如果G中恰好有v-1条边，则G一定是树吗

是的，如果一个具有v个节点的无向图G中恰好有v-1条边，那么G一定是一棵树。这是因为树是一种无向连通图，并且没有环。而一个具有v个节点的树，恰好有v-1条边。

如果一个无向图G不是树，那么它必然存在环，所以边的数量一定大于等于节点数量。如果一个无向图G恰好有v-1条边，那么G一定是连通的（因为如果不连通，那么边的数量要小于v-1），并且没有环。因此，它必定是一棵树。

相关问题

具有v个节点的无向图G，如果G中的每对结点间都相互可达，则G一定是树吗

如果一个无向图G中的每对结点间都相互可达，那么G一定是一棵树吗？

不一定。虽然一个无向图中每对结点间相互可达是树的一个重要特征，但仅仅满足这个条件并不能保证这个无向图是一棵树。例如，下面这个图：

   A
 /   \
B     C
 \   /
  D-E

该图中的每对结点间都相互可达，但它并不是一棵树。因为它有一个环，即D-E-C-A-B-D。所以，满足相互可达并不足以说明这个图是一棵树。

总之，一个无向图G如果是树，那么其中每对结点间相互可达；但反过来，并不是每个满足相互可达的无向图都是树。

如果无向完全图G中有45条边，则G的生成树有 多少条边

无向完全图 G 中有 n 个节点，则 G 中的边数为 n(n-1)/2。若 G 有 45 条边，则 n(n-1)/2=45，解得 n=10。在一个无向完全图中，任意 n 个节点的生成树的数量为 n^(n-2)。因此，在这个无向完全图 G 中，生成树的边数为 9，即生成树的数量为 10^(8-2)=10^6。