定理610五色定理):任何平面图G是5 可着色的。 证明:不妨设G是平面简单图。下面对G的顶 点数采用归纳法证明。 当n≤5时结论显然成立 假设对n-个顶点的所有平面简单图G是5可着 色的。 考虑n个顶点的平面简单图G, 由定理6知,G中存在顶点v,使d(v)≤5 删去v及其关联边得到G=Gv0 由归纳假设,G-v是5可着色的, 在给定G-v的一种着色后,将v及其关联边加 回到原图中,得到G
定理 6.10(五色定理)：任何平面图G是5- 可着色的。 证明：不妨设G是平面简单图。下面对G的顶 点数采用归纳法证明。 当n5时结论显然成立 假设对n-1个顶点的所有平面简单图G是5-可着 色的。 考虑n个顶点的平面简单图G, 由定理 6.2知, G中存在顶点v0 ,使d(v0 )5。 删去v0及其关联边得到G'=G-v0 由归纳假设, G- v0是5-可着色的, 在给定G- v0的一种着色后, 将v0及其关联边加 回到原图中, 得到G
(1)d(vo)<5, (2)d(vo)=5 定理61(c色定理):地图G是2面可着 色的当且仅当它是一个欧拉图。 证明:(1)G是2-面可着色的,则它是一 个欧拉图 (2)G是欧拉图,则G是2-面可着色的
(1)d(v0 )<5, (2)d(v0 )=5 定理 6.11(二色定理)：地图G是2-面可着 色的当且仅当它是一个欧拉图。 证明：(1) G是2-面可着色的，则它是一 个欧拉图 (2) G是欧拉图，则G是2-面可着色的
第七章树 71树及其性质 定义71:一个连通无回路的图称为树, 记为T。树中度数为1的顶点称为树叶(或 称悬挂点)。度数大于1的顶点称为分枝 点或内点。不相交的树的全体称为森林。 平凡图也可称为平凡树。(平凡图即只有 一个点)
第七章 树 7.1树及其性质 定义 7.1：一个连通无回路的图称为树, 记为T。树中度数为1的顶点称为树叶(或 称悬挂点)。度数大于1的顶点称为分枝 点或内点。不相交的树的全体称为森林。 平凡图也可称为平凡树。(平凡图即只有 一个点)
图a)是一棵树;(b是森林也就是无回 路的图,它的每个分支是一棵树
图 (a)是一棵树；(b)是森林,也就是无回 路的图,它的每个分支是一棵树
除了定义71给出树的定义外还有几个树的等 价定义,即下面的定理。 定理71:设图T有n个顶点有下列6条T是树的 等价定义: (1)T是无回路的连通图; (2T是无回路图,且e=n-1,其中e是边数; (3)T是连通图,且e=n-1; (4)T是无回路图且在T的任两个不相邻的顶点 之间添加一边,恰得到一条回路(称T为最大无回 路图); (5T是连通图,但删去任一边后,便不连通(称T 为最小连通图); (6)T的每一对不同的顶点之间有唯一的一条路
除了定义 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是无回路的连通图, 显然只能是下图所示: 故结论成立。 假设n=k时结论成立现考察n=k+1时,由于连通无回路以 及定理54 (若图G中每个顶点度数至少为2,则G包含一条回路), 可以知道至少有一个顶点度数为的点u它的关联边为 uv}
证明：(1)→(2): T是无回路的连通图要证明T是无回路 图,且e=n-1，即证明e=n-1 对顶点数n采用归纳法,n=2时,因为T是无回路的连通图， 显然只能是下图所示： 故结论成立。 假设n=k时结论成立,现考察n=k+1时,由于连通无回路以 及定理 5.4 (若图G中每个顶点度数至少为2,则G包含一条回路), 可以知道至少有一个顶点度数为1的点u,它的关联边为 {u,v}
(2)→(3):T是无回路图,且e=n-1,要证明T是连通 图,且e=n-1。即证明T是连通图用反证法
(2)→(3): T是无回路图,且e=n-1,要证明T是连通 图,且e=n-1。即证明T是连通图,用反证法
(3)→(4):在T是连通图,且e=n-的条件下, 证明T是无回路图且在T的任两个不相邻 的顶点之间添加一边,恰得到一条回路。 1)首先证明T是无回路的。 对顶点数n采用归纳法, n=2时e=1,且连通,只能是下图 显然T是无回路的
(3)→(4):在T是连通图,且e=n-1的条件下, 证明T是无回路图,且在T的任两个不相邻 的顶点之间添加一边,恰得到一条回路。 1)首先证明T是无回路的。 对顶点数n采用归纳法, n=2时e=1,且连通, 只能是下图 显然T是无回路的
假设n=k-1时结论成立,考察n=k时,由于T是连通 的,所以每个顶点度数≥(e=k-1)。可以证明至少 存在一个顶点u,使d(u)=1。Why?
假设n=k-1时结论成立,考察n=k时,由于T是连通 的,所以,每个顶点度数1(e=k-1)。可以证明,至少 存在一个顶点u,使 d(u)=1。Why?
2)再证明如果在连通图T的任两个不相邻 顶点之间添加一边,记为{vp,则该边与T 中从v到v的一条路 iyvi1…, Vissr 构成一条回路vpv"…,vs,vv) 若这条回路不唯一,由于T无回路,而 TU{,v}得到了回路,因此另一条回路C 也含有边{v,}
2)再证明如果在连通图T的任两个不相邻 顶点之间添加一边,记为{vi ,vj },则该边与T 中从vi到vj的一条路 (vi ,vi1 ,…, vis,vj ) 构成一条回路(vi ,vi1 ,…, vis,vj ,vi )。 若这条回路不唯一，由于T无回路，而 T∪{vi ,vj }得到了回路，因此另一条回路C' 也含有边{vi ,vj }