定理2 设G为一个至少具有三个结点的连通平面图,则G中必.ppt

《定理2 设G为一个至少具有三个结点的连通平面图,则G中必.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、定理2设G为一个至少具有三个结点的连通平面图，则G中必有一个结点u，使得deg(u)≤5。证明设G=，

2、V

3、=v，

4、E

5、=e，若G的每一个结点u都有deg(u)≥6，但因deg(vi)=2e故2e＞6v，所以e≥3v＞3v―6，与欧拉定理矛盾。vi=1定理3任意平面图G最多是5-色的。证明给定平面图G=，对结点数v用归纳法。a）当v=1，2，3，4，5时显然成立。b）设v=k时成立，现考察v=k＋1，由定理2可知，必存在结点u，使deg(u)≤5,在图G中删去u，得到G―{u}，由归纳假设知此时定理成立。现将u加入到G―{u}中，若deg(u)<5，则与u

6、邻接的结点数不超过4，故必可对u正常着色，得到一个最多是五色的图G。若deg(u)=5，设与u邻接的结点，按逆时针排列为v1,v2,v3,v4,v5,它们分别着不同的颜色C1,C2,C3,C4,C5。令H为G―{u}中所有着C1与C3色的结点集合，F为G―{u}中着C2与C4的所有结点的集合。Ⅰ：若v1与v3属于结点集H所导出子图的两个不同的连通分支中，将v1所在分图中的C1,C3两种颜色对调，并不影响图G―{u}的正常着色，然后在u上着C1色，即得图G是五色的。Ⅱ：若v1与v3属于结点集H所导出子图的同一个连通分支中，那么从v1到v3必有一条路P，P上的各个结点都是着C1或C

7、3色。路P与边(u,v1)、(u,v3)一起构成了一条回路L,它包围了v2或v4，但不能同时包围v2和v4，故v2和v4分别属于结点集F所导出子图的两个不同连通分支中。因此在包含v2的连通分支中将C2和C4颜色对调并不会影响G―{u}的正常着色，那样，点v2与v4都着了C4色，故对u着C2色。即可得到五色图G。