(1)d(v0)<5,(2)d(v0)=5定理6.11(二色定理)：地图G是2-面可着色的当且仅当它是一个欧拉图。证明：(1)G是2-面可着色的，则它是一个欧拉图(2)G是欧拉图，则G是2-面可着色的第七章树图(a)是一棵树；(b)是森林,也就是无回路的图,它的每个分支是一棵树。除了定义7.1给出树的定义外还有几个树的等价定义,即下面的定理。定理7.1：设图T有n个顶点,有下列6条T是树的等价定义:(1)T是无回路的连通图;(2)T是无回路图,且e=n-1,其中e是边数;(3)T是连通图,且e=n-1;(4)T是无回路图,且在T的任两个不相邻的顶点之间添加一边,恰得到一条回路(称T为最大无回路图);(5)T是连通图,但删去任一边后,便不连通(称T为最小连通图);(6)T的每一对不同的顶点之间有唯一的一条路。证明：(1)→(2):T是无回路的连通图要证明T是无回路图,且e=n-1，即证明e=n-1对顶点数n采用归纳法,n=2时,因为T是无回路的连通图，显然只能是下图所示：(2)→(3):T是无回路图,且e=n-1,要证明T是连通图,且e=n-1。即证明T是连通图,用反证法,(3)→(4):在T是连通图,且e=n-1的条件下,证明T是无回路图,且在T的任两个不相邻的顶点之间添加一边,恰得到一条回路。1)首先证明T是无回路的。对顶点数n采用归纳法,n=2时e=1,且连通,只能是下图假设n=k-1时结论成立,考察n=k时,由于T是连通的,所以,每个顶点度数1(e=k-1)。可以证明,至少存在一个顶点u,使d(u)=1。Why?2)再证明如果在连通图T的任两个不相邻顶点之间添加一边,记为{vi,vj},则该边与T中从vi到vj的一条路(vi,vi1,…,vis,vj)构成一条回路(vi,vi1,…,vis,vj,vi)。若这条回路不唯一，由于T无回路，而T∪{vi,vj}得到了回路，因此另一条回路C'也含有边{vi,vj}，(4)→(5):在T是无回路图,且在T的任两个不相邻的顶点之间添加一边,恰得到一条回路的条件下证明T是连通图,但删去任一边后,便不连通。若T不连通,则存在顶点vi和vj,在vi与vj之间没有路。显然,若加一边{vi,vj},不会产生回路,与假设矛盾。又由于T无回路,则删去任一边,便不连通(5)→(6):在T是连通图,但删去任一边后,便不连通的条件下证明T的每一对不同的顶点之间有唯一的一条路。由于T是连通的,任两点之间有一条路。如果某两个顶点之间多于一条路,则T中必含有回路,(Why?)删去该回路上任一边,图仍连通,与假设矛盾。(6)→(1):在T的每一对不同的顶点之间有唯一的一条路的条件下，证明T是无回路的连通图。显然图是连通的。若有回路,则回路上任两点之间有两条路,从而导致矛盾。推论：若G是n个顶点个分支的森林,则G有n-条边。定理7.2:在任一棵非平凡树T中,至少有两片树叶。证明:由于T是连通的,对T的任一顶点vi,d(vi)1,并且e=n-1,即所有顶点度数之和=2(n-1).下面证明T中至少有两个顶点的度数为1。7.2生成树与割集例如下图中给定图G,粗线表示G的生成树T,它的边集是{e1,e4,e5,e6},的边集是{e2,e3,e7,e8}。定理7.3：G是连通图当且仅当G有生成树。证明：1)G有生成树证明G是连通图。因为生成树是连通图,生成子图连通，则原图一定连通。2)G是连通图证明G有生成树设G是连通图,若G没有回路,则G本身就是生成树；若G只有一条回路,从这条回路中删去一条边,仍保持连通,得到一棵生成树；若G中有多条回路,则重复上述过程,直到得到一棵生成树为止。设连通图G有n个顶点,e条边,那么G的任一棵生成树有n-1条枝,e-n+1条连枝。设图G有n个顶点,e条边,个分支,n,e,之间有两个简单的关系式:n-0;e-n+0。定义7.3:设图G有n个顶点,e条边,个分支,称n-为G的秩,称e-n+为图G的零度。显然G的秩是G的各分支中生成树的枝数之和,G的零度是G的各分支中生成树的连枝数之和。对于连通图G来说,它的秩为n-1,零度为e-n+1。二、割集与断集定义7.4：设D是图G的一个边集,若在G中删去D的全部边后所得图的秩减少1,而删去D的任何真子集均无此性质,称D为G的割集。图(b)中边集{e1,e2}是割集边集{e1,e2,e3,e4}不是割集,定义7.5:设图G的顶点非空真子集为V1V,在G中一个端点在V1中,另一端点在V(G)-V1中的所有边组成的集合称为G的一个断集或称边割,记为E(V1(V(G)-V1)),简记为(V1,V(G)-V1)。当|(V1,V(G)-V1)|=1时,(V1