Question

有n个顶点的无向图至多有多少条边？

Answer 1

9个，连通图n(n-1)/2=28，解得n=8，非连通至少还有一个点，一共9个。

证明：

假设有8个顶点，则8个顶点的无向图最多有28条边且该图为连通图

连通无向图构成条件：边=顶点数*（顶点数-1）/2

顶点数>=1，所以该函数存在单调递增的单值反函数

所以边与顶点为增函数关系

所以28个条边的连通无向图顶点数最少为8个

所以28条边的非连通无向图为9个（加入一个孤立点）

无向图的表示

【例】G2和(c)图中的G3均是无向图，它们的顶点集和边集分别为：

V(G2)={v1，v2，v3，v4}

E(G2)={(vl，v2)，(v1，v3)，(v1，v4)，(v2，v3)，(v2，v4)，(v3，v4)}

V(G3)={v1，v2，v3，v4，v5，v6，v7}

E(G3)={(v1，v2)，(vl，v3)，(v2，v4)，(v2，v5)，(v3，v6)，(v3，v7)}

以上内容参考：百度百科-无向图