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

适用条件

• G 是无向图。
• G 有 n 个顶点。
• 我们寻找可能的最大边数。

理解与推导

1. 识别每个顶点可以连接到其他 n-1 个顶点。
2. 对所有 n 个顶点的连接数求和，得到 $n(n-1)$。
3. 除以 2，因为每条无向边被计算了两次（每个端点各一次）。
4. 得出最大边数为 $n(n-1)/2$ 的结论。

例子

对于一个包含 5 个顶点的完全图，演讲者将边数计算为 $4+3+2+1$，等于 $5*4/2 = 10$。这推广到 n 个顶点的 $n(n-1)/2$。

容易误解的地方

• 将无向图的最大边数与有向图的最大边数（$n(n-1)$）混淆。
• 假设连通图必须是完全图，而实际上连通图只要求顶点之间有路径，不需要直接相邻。

观看对应讲解

继续追问

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