为什么具有 n 个顶点的非连通无向图最多有 (n-1)(n-2)/2 条边？

适用条件

• G 是无向图。
• G 有 n 个顶点。
• G 是非连通图。

理解与推导

1. 分离出一个顶点使其保持孤立，以确保图是非连通的。
2. 将所有剩下的 n-1 个顶点相互连接，形成一个完全子图。
3. 使用 n-1 个顶点的公式计算这个完全子图中的边数：(n-1)((n-1)-1)/2。
4. 将表达式简化为 (n-1)(n-2)/2。

例子

演讲者构造了一个包含 6 个顶点（A, B, C, D, E, F）的例子。顶点 A 到 E 形成一个完全图（$5*4/2 = 10$ 条边），而 F 是孤立的。这与公式 (6-1)(6-2)/2 = 10 相符。

容易误解的地方

• 错误地假设孤立顶点可以与其他顶点连接而不违反非连通性。
• 仅依赖演讲者的口头解释，他错误地将公式说成 $n(n-1)(n-2)/2$，而不是屏幕上正确的公式 (n-1)(n-2)/2。

观看对应讲解

继续追问

• 为什么具有 n 个顶点的无向图最多有 $n(n-1)/2$ 条边？
• 具有 n 个顶点的有向图最多有多少条边？
• 为什么具有 n 个顶点的连通无向图至少需要 n-1 条边？