平面图和五色定理

平面图和五色定理第一页，共三十六页，2022年，8月28日

abcdf

ghxk

ya1b1c12df31hx31kg22y

第二页，共三十六页，2022年，8月28日6.2

平面图和五色定理定义6.2.1如果能与这样的一个图同构，其中的顶点在同一个平面上，而的边只能在端点处相交，就称为平面图，而称为的一个平面嵌入，或称为在平面上的实现。如图和就不具有这样的性质。一、平面图的概念及性质

第三页，共三十六页，2022年，8月28日定义6.2.2平面图的边把整个平面分割成若干各连通的区域，这些区域的闭包称为平面图的面（包括外部无限区域，称为外部面）。分别用和表示的面的集合和面的个数。定义6.2.3用表示平面图中围成面的周界。用（或）表示围成面的周界的边数，称为的度。第四页，共三十六页，2022年，8月28日在任何平面图中，度为奇数的面的个数为偶数。定理6.2.1如果G是平面图，则第五页，共三十六页，2022年，8月28日问题：一个平面图的面数是否会随着这个平面图的不同嵌入而改变？第六页，共三十六页，2022年，8月28日

定理6.2.3（Euler公式）设是一个有个顶点、条边和个面的连通平面图，则

第七页，共三十六页，2022年，8月28日证明：对面数进行归纳证明。由于是连通的平面图，所以当时，是树，因此。故

假设对于一切面数少于的所有连通平面图，Euler公式成立。现假设是一个有个顶点、条边和个面的连通图。由于，至少有一个回路，取这回路中的一条边，则仍是连通平面图，有个顶点，条边和个面，根据归纳假设。即证毕。第八页，共三十六页，2022年，8月28日问题：对于非连通的平面图，其相应的点数、边数和面数有什么关系？第九页，共三十六页，2022年，8月28日推论6.2.4若是阶为的平面图，的最短回路的长度为，则证明：现在对的每个面，由于假设，因此

由定理6.2.1知

不妨设该平面图是连通的平面图，则根据Euler公式，有因此，有第十页，共三十六页，2022年，8月28日推论的一般情况：对简单平面图，有由以上结论，容易验证和不是平面图第十一页，共三十六页，2022年，8月28日

设是简单平面图，则。证明：反证法。假设是一个平面图，但，则而对于简单平面图，有矛盾。故对每一个简单平面图，有。第十二页，共三十六页，2022年，8月28日例：平面上有个点，其中任意两个点之间的距离至少是1。证明在这个点中，距离恰好为1的点对数至多是。第十三页，共三十六页，2022年，8月28日二、平面图与正多面体

凸多面体在平面上的投影是一个连通的平面图，因此Euler公式也适用于凸多面体。为此我们可以用Euler公式讨论正多面体。第十四页，共三十六页，2022年，8月28日正4-面体第十五页，共三十六页，2022年，8月28日正6—面体第十六页，共三十六页，2022年，8月28日正8-面体—抽象化—第十七页，共三十六页，2022年，8月28日—抽象化—正12-面体第十八页，共三十六页，2022年，8月28日—抽象化—正20-面体第十九页，共三十六页，2022年，8月28日定理

存在且只存在5种正多面体：正四面体、正方体、正八面体、正十二面体和正二十面体。第二十页，共三十六页，2022年，8月28日证明：首先一个正多面体在平面上的投影所得平面图是2连通的正则图，而且每个面的度相同，即为。设平面图是正则、每个面的度为，则，，并且

即满足上式且至少为3的正整数和只有五对。（见下表）第二十一页，共三十六页，2022年，8月28日相应的正多面体33464正4-面体348126正6-体35203012正12-面体436128正8-面体53123020正20-面体第二十二页，共三十六页，2022年，8月28日正4-面体正8-面体正6-面体正12-面体正20-面体平面上看：第二十三页，共三十六页，2022年，8月28日三、平面图的判别

我们可以利用和的非平面性来给出两个有关平面图的判别定理第二十四页，共三十六页，2022年，8月28日找出一个图是平面图的充分必要条件的研究持续了几十年，直到1930年波兰数学家库拉托夫斯基（Kuratowski）给出了平面图的一个非常简洁的特征。给定图的一个剖分是对图实现有限次过程而得到的另一个图:即删去的一条边后，添一个新的顶点及两条新的边、。也就是说在的边上插入有限个顶点便可得到的一个剖分。第二十五页，共三十六页，2022年，8月28日定理6.2.7（Kuratowski定理）图是平面图当且仅当它的任何子图都不是或的剖分。定理6.2.8（Wangner定理）一个图为平面图当且仅当它的任何子图都不能收缩为或。可得Petersen图不是平面图。收缩边第二十六页，共三十六页，2022年，8月28日四、五色定理的证明我们将利用推论的结论来证明每一个平面图的点色数不超过5第二十七页，共三十六页，2022年，8月28日

每一个平面图的色数不超过5。

证明：对平面图的顶点数进行归纳。当时，结论显然成立。不妨假设所给的平面图连通。归纳假设对顶点数为的平面图结论成立，下设是顶点数为的简单图。设法证明。反证法：设。首先由推论6.2.5知，设，。作。此时是阶为的平面图，由归纳假设得。如果，只要将五种颜色分配给，即可得，矛盾，故。设已给的顶点染五种颜色，使中相邻顶点染以不同的颜色。

第二十八页，共三十六页，2022年，8月28日如果，可得矛盾。。设的五个邻点依次为。分两种情况：Case1五个点所染颜色有相同的，只要将在没出现的颜色分配给，就有。矛盾。Case2五个点染得颜色各不相同。不妨设分别染。让为的色划分。现考虑的子图。如果在中与不在同一个连通分支中，则可以把中含的连通分支内的与两种颜色互换，而中其余颜色不变，就得到的一个5染色。此时与同染这种颜色，与假设矛盾。所以与在同一连通分支中，于是在中存在一条到的路第二十九页，共三十六页，2022年，8月28日同样考虑子图，在中存在到的路。由路的构造可知，与不相交（即无公共顶点）。但在中，回路将与分隔在两个不同的区域内，而是平面图，所以路必与相交于某个顶点。由于，因此与相交与某个顶点，矛盾。证毕。第三十页，共三十六页，2022年，8月28日一个非平面图G是不能嵌入在一个平面上的，但它可以分解为若干个平面图的并图，即存在若干平面图使，不妨设这些平面图是G的生成子图，我们将这种平面图分解的最小个数称为G的厚度，记为，于是当且仅当是平面图。五、非平面图的分解问题第三十一页，共三十六页，2022年，8月28日第三十二页，共三十六页，2022年，8月28日定理6.2.10

设是具有围长的一个非平面图，则其中表示不小于的最小整数。第三十三页，共三十六页，2022年，8月28日证明：设非平面图的厚度为，则存在平面图，使这里是的生成子图。则每个生成子图是围长至少为的平面图，由推论6.2.4，有故有

第三十四页，共三十六页，2022年，8月28日例1对于那些n，存在n条棱的凸多面体？（1968年波兰数学奥林匹克试题）解：以多面体的顶点为图的顶点，以多面体的棱为图的边，组成一个平面图G,则，每个面的度至少是3。由Euler公式，，即没有棱数小于6的凸多面体。四面体是棱数为6的凸多面体。若有7条棱的凸多面