G 是简单图，E(G) 是图中的边数，V(G) 是图中的顶点数，证明：E(G)≤C(V(G),2)

wilsony

谁能证明？

luyuanhong

题  G 是简单图，E(G) 是图中的边数，V(G) 是图中的顶点数，证明：E(G)≤C(V(G),2) 。

证  图 G 中共有 V(G) 个顶点，如果在图中任何两个顶点之间，都连一条边，则总共可连

               V(G)×[V(G)-1]／2 = C(V(G),2) 条边。

    因为 G 是简单图，两点之间最多连一条边，不可能再有其他的边了，所以图中的边数

                  E(G)≤C(V(G),2) 。

wilsony

这道题不难，谢谢陆老师费心解答。