定理1无向图T是树，当且仅当以下五条之一成立。（1）T中无回路且m=n-1,其中m为边数，n为顶点数。（2）T是连通图且m=n-1。（3）T中无回路，但增一条边，则得到一条且仅一条初级回路。（4）T连通且每条边均是桥。（5）每对顶点间有唯一的一条初级通路。证明由树的定义可得（1）。对顶点数n作归纳。当n=1时，m=0,则m=n-1成立。假设当n=k时，m=n-1成立。则当n=k+1时，因为树是连通的且无回路，所以 至少有一个度数为1的顶点V,从树中删去v和与它关联的边，则得到k个顶点的树。根 据假设它有k-1条边，现将v和与它关联的边加到T上还原成树T,则T有k+1个顶点，k 条边，边数比顶点数少1,故m=n-1成立 由（1）可得（2）。再证反证法，若图T不连通，设T有k个连通分支T1, T2,，Tk （k2）,其顶点 数分别为n1, n2,nk,则有nl+n2+.+nk=n边数分别为m1, m2,，mk,则有m1+m2+.+mk=n其中：m1=n1-1,m2=n2-2,mk=nk-1.因此，有 m=n1+n2+nk -k=n-k1,并且至少有一个顶点vO,满足d （v0） =1。否则，如果每个顶点v都有 d （v） 2,那么必然会有总度数2m2n,即mn,这与条件m=n-1矛盾。因此至少有一个 顶点vO,满足d （vO） =1。删去vO及其关联的边，得到图T,由假设知T无回路，现将vO及其关联的边再加到T, 则还原成T,所以T没有回路。如果在连通图T中增加一条新边（vi, vj）,贝l（vi, vj）与T中从vi到vj的一条 初级路径构成一个初级回路，且该回路必定是唯一的，否则当删去新边（vi, vj）时，T中 必有回路，产生矛盾。 由（3）可得（4）。若图T不连通，则存在两个顶点vi和vj,在vi, vj之间没有路径，如果增加边（vi, vj）不产生回路，这与（3）矛盾，因此T连通。因为T中无回路，所以删去任意一条边， 图必不连通。故图中每一条边均是桥。 由（4）可得（5）。由图的连通性可知，任意两个顶点之间都有一条通路，是初级通路。如果这条初 级通路不唯一，则T中必有回路，删去回路上的任意一条边，图仍连通，与（4）矛盾。故 任意两个顶点之间有唯 条初级回路由 （5 ）可得树的定义。每对顶点之间有唯一一条初级通路，那么T必连通，若有回路，则回路上任意两 个顶点之间有两条初级通路，与（5）矛盾。故图连通且无回路，是树。定理2任何一棵n阶非平凡树T至少有两片树叶。证明：设T是（n, m）图，n2，有k片树叶，其余顶点度数均大于或等于2。则由握 手定理：顶点度数之和等于边数的2倍和树中m=n-1得2m=2（n-l）2（n-k）+k得所以2n-22n-k，即Q2,因此任一棵n阶非平凡树T至少有两 片树叶。定理3无向图G有生成树的充分必要条件是G为连通图。证明：先采用反证法来证明必要性。若G不连通，则它的任何生成子图也不连通，因此不可能有生成树，与G有生成 树矛盾，故G是连通图。再证充分性。设G连通，则G必有连通的生成子图，令T是G的含有边数最少的生成子图，于 是T中必无回路（否则删去回路上的一条边不影响连通性，与T含边数最少矛盾），故T是 一棵树，即生成树。习题：1、设T是无向图G的生成树，T是T的余树，证明T中不含G的割集（这里指的是边割 集）。证明:因为G的生成树T和T的余树没有共公边，T的割集是生成树T中的边，因 此T中不含T的割集，如果T中含T的割集，则删去T中的边后也就连割集中的边也删去, 而此时T还是连通的，这与割集的定义矛盾，因此T中不含G的割集。证明：因为T是正则二叉树，所以T的每个分支点的出度均为2. 由于所有结点入度之和等于所有结点出度之和T中所有结点出度之和等于2iT中所有结点入度之和等于i+t因此 2i=i+t-1 得 i=t-1所以T中的结点数为：i+t=2t-1所以T是2t1阶树或另证：T中的边数为2i,结点数为i+t，由边数=结点数-1得2i=i+t-1，所以 i=t 1所以T中的结点数为：i+t=2t-1所以T是2t1阶树