定理1：设图G是一个具有n个顶点的连通图，则其边数 e≥n-1 证明：不妨设G是简单图（没有重边，没有环）。若n=1,则e=0, 结论成立！若G至少有2个顶点，则取V,={v,},则存在一条边e,∈ [V,V](边的一个端点属于V,另外一个端点属于V,的补)。记evV2, 则再取V2{v,V2}。 若V2是V(G)的真子集，则存在e2∈[V2,V2]。记ev2v3,则再取 V={v,V2,V}。按照这个过程继续下去，最后必定在取到n-1条边 e1,e,…,e1后得到集合V。={V1,V2,V3,…,Vn}=V(G),从而该迭代操作 终止。因此，图G至少有-1条边。 定理 1：设图 G 是一个具有 n 个顶点的连通图，则其边数 e≥n-1 证明：不妨设 G 是简单图（没有重边，没有环）。若 n=1，则 e=0， 结论成立！若 G 至少有 2 个顶点，则取 V1 ={v1},则存在一条边 e1∈ [V1,V1]（边的一个端点属于 V1，另外一个端点属于 V1的补）。记 e1 =v1v2, 则再取 V2={v1,v2}。 若 V2是 V(G)的真子集,则存在 e2∈[V2,V2]。记 e2=v2v3,则再取 V3 ={v1,v2,v3}。按照这个过程继续下去，最后必定在取到 n-1 条边 e1,e1,…,en-1后得到集合 Vn ={v1,v2,v3,…,vn}=V(G)，从而该迭代操作 终止。因此，图 G 至少有 n-1 条边