为什么具有 n 个顶点的连通无向图至少需要 n-1 条边？
为了确保任意两个顶点相互可达，图必须至少有 n-1 条边。当图形成树状结构（如星形图）时，可以达到这个最小值，此时边连接顶点而不形成环。
适用条件
- G 是无向图。
- G 有 n 个顶点。
- G 是连通图。
理解与推导
- 考虑一个有 n 个顶点的图。
- 为了在不产生冗余的情况下连接所有顶点，逐一添加边以连接孤立的顶点或分量。
- 将 n 个顶点连接成一个连通分量所需的最少边数是 n-1。
- 用星形图例子验证：5 个顶点需要 4 条边才能保持连通。
例子
演讲者画了一个包含 5 个顶点（A, B, C, D, E）的星形图，其中中心顶点 C 连接到其他四个顶点。这恰好使用了 4 条边（n-1）来使整个图连通。
容易误解的地方
- 将“连通”误认为“任意两个顶点必须直接相邻”，这将需要 条边（完全图）。
- 假设少于 n-1 条边仍能形成连通图，这实际上会导致至少一个顶点孤立。
观看对应讲解
继续追问
答案依据视频资料生成并经过独立核验。若有疑问，请核对原视频或联系原作者。