algorithm - 可以选择 n-1 条边以形成具有 n 个节点的连通图的方式的数量

Question

基本上，您需要 n-1 条边，才能创建具有 n 个节点的连通图。我想知道是否有任何理论支持从可能的总 n(n-1)/2 条边中找到可以选择 n-1 条边的不同方法的数量，以便图形保持连接。

Answer 1

正好有n<sup>n-2</sup>带顶点集的连通图 {1,...n}对于 n > 0 .此结果称为 Cayley's Formula .