定理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的每一对不同的顶点之间有唯一的一条路