树中边和点的数量关系 。设T是树，令n=|Vl,m=El,则m=n-l。 证明.对n进行归纳证明。当n=l,T是平凡树，结论显然成立。 假设当n≤k是结论成立。 若n=k+l。因为T中每条边都是割边，任取eeET-{e}含两 个连通分支，设其为T,T,并设它们边数分别是m1,m2, 顶点数分别是n1,n2,根据归纳假设：m1=n1-1,m2n21。 注意：n1+n2n,m1+m2m-l。 ∴.m=m,+m,+1=n-1
树中边和点的数量关系 设T是树，令n=|VT |, m=|ET |, 则m=n-1。 证明. 对n进行归纳证明。当n=1, T是平凡树，结论显然成立。 假设当nk是结论成立。 若n=k+1。因为T中每条边都是割边，任取eET , T-{e}含两 个连通分支，设其为T1 , T2 , 并设它们边数分别是m1 , m2 , 顶点数分别是n1 , n2 , 根据归纳假设：m1 =n1 -1, m2 =n2 -1。 注意：n1 +n2 =n, m1 +m2 =m-1。 m= m1 +m2 +1=n-1
急售房 连通图边数的下限 。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（ n2）的连通图，其边数mn-1。 (对于树，m=n-1, “树是边最少的连通图”) 证明：对n进行一般归纳。当n=2时结论显然成立。 设G是边数为m的连通图，且|VG |=n>2。任取vVG，令 G’=G-v,设G’有(1)个连通分支G1 ,G2 ,…,G，且Gi的边数 和顶点数分别是mi和ni。 我们有n=n1 +n2 +…+n +1, mm1 +m2 +…+m + (每个连通分 支中至少有一个顶点在G中与删除的v相邻)。 由归纳假设，mi ni -1(i=1,2,…)。 所以：m m1 +m2 +…+m +n1 +n2 +…+n -+=n-1
与边点数量关系有关的等价命题 设T是简单无向图，下列三个命题等价： (1)T是树。 (2)T不含简单回路，且m=n-1。 (3)T连通，且m=n-1。 。(1)→(2)，已证。 ·(2)→(3)，若不连通，分支数o0≥2，各分支为树（无简单回 路、连通)，则m=n-0<n-1,矛盾。 ●(3)→(1)，设e是T中任意一条边，令T'=T-e,且其边数和顶点 数分别是m和n,则m'=m-1=n-2<n-1,.T”是非连通图。因 此，G的任意边均不在简单回路中，.G中无简单回路
与边点数量关系有关的等价命题 设T是简单无向图，下列三个命题等价： (1) T是树。 (2) T不含简单回路，且m=n-1。 (3) T连通，且m=n-1。 (1)(2), 已证。 (2)(3), 若不连通，分支数2，各分支为树（无简单回 路、连通），则m=n-<n-1，矛盾。 (3)(1), 设e是T中任意一条边，令T’=T-e, 且其边数和顶点 数分别是m’和n, 则m’=m-1=n-2<n-1, T’是非连通图。因 此，G的任意边均不在简单回路中，G中无简单回路