急售房 连通图边数的下限 。J顶点数为n（n≥2)的连通图，其边数mm-l。 (对于树，m=n-1,“树是边最少的连通图”) 。证明：对n进行一般归纳。当n=2时结论显然成立。 设G是边数为m的连通图，且IVc=n>2。任取veVc,令 G’=G-y,设G有o(o≥1)个连通分支G1,G2,…,G。,且G的边数 和顶点数分别是m和n。 我们有n=n1+n2+..+n。+1,m≥m1+m2+..+m。+0(每个连通分 支中至少有一个顶点在G中与删除的v相邻)。 由归纳假设，m2n-1(=1,2,.o)。 所以：m2m1+m2+..+mo+0≥n1+n2+..+no0+0=n-1。连通图边数的下限  顶点数为n（ n2）的连通图，其边数mn-1。 (对于树，m=n-1, “树是边最少的连通图”)  证明：对n进行一般归纳。当n=2时结论显然成立。 设G是边数为m的连通图，且|VG |=n>2。任取vVG，令 G’=G-v,设G’有(1)个连通分支G1 ,G2 ,…,G，且Gi的边数 和顶点数分别是mi和ni。 我们有n=n1 +n2 +…+n +1, mm1 +m2 +…+m + (每个连通分 支中至少有一个顶点在G中与删除的v相邻)。 由归纳假设，mi ni -1(i=1,2,…)。 所以：m m1 +m2 +…+m +n1 +n2 +…+n -+=n-1