12 Do Not Cross. Planar Graphs
Euler's Theorem for Planar Graphs
考虑三个房子和三个水井，假设三个房子住的人互相看不上，那么我们需要修九条连通三个房子和三个水井，要求九个路线不交叉以避免他们遇见。
图12.1是一个失败的尝试。
这个问题是无解的，后面会给出证明。
这一章会聚焦于新的问题：边不相交。
Definition 12.1. 图能够被画在平面上且任意两条边都不相交，那么被称为平面图(planar graph)。
图的边把平面划分成若干区域，这些区域是的面(face)。图12.2是一个例子。
平面图的面的个数和图的顶点、边的数量一样重要。下面的定理表明了三者的关系。
Theorem 12.2 (Euler's Theorem on Planar graphs). 图是一个有个顶点、条边、个面的连通平面图，那么。
Proof. 基于递归。时，要么是一个只有一条边的树，那么；要么是一个点加一个环的图，那么，都有。
假设对于所有有条边的连通平面图都成立，考虑有条边的图。分两种情况讨论。
1) 移除的一条边新生成的图仍旧连通，那么在一个环上。环将分割称两个面，但是去掉边后，两个面变成了一个面。所以有条边、个顶点和个面。由递归假设知，所以。
2) 如果不存在上面所说的边，那么无环，即一棵树。由Theorem 10.4有，又因为只有一个面，所以命题成立。
现在我们回到三个房子和三个水井的问题。问题等价于在平面上能不能画出，同时没有边交叉。
Example 12.3. 图不是平面图。
Solution. 反证法。假设是平面图，有九条边和六个顶点，根据Theorem 12.2可以计算得到有五个面。是完全二分图，所有的面都必须是四边形，那么五个面有二十条边，又有每条边被两个面共有，那么五个面需要十条边，但是只有九条边。
由于是的子图，那么也不是平面图。是三角形，明显是平面图。也是容易画出来的，四边形，连接一条对角线，另外一对顶点从外围相连，所以是平面图。是不是平面图就不那么显而易见了。
Example 12.4. 不是平面图。
Solution. 和上个题目类似的解法。假设是平面图，有五个顶点，十条边，那么计算得到有七个面。是完全图，所以每个面必须是三角形。七个三角形二十一条边，两个面共享一条边，那么和只有十条边矛盾。
这里讲和是有原因的。实际上，这两种图是导致图不是平面图的唯二原因。
如果不是平面图，移除度为二的点，使得边称为一条边，新的图仍旧不是平面图。类似的，我们将图的边之间插入一个点，分成两条边，这次得到的新图也不是平面图。如果图能够从中重复这两种操作得到，那么和是edge-equivalent的。
Theorem 12.5 (Kuratowski's Theorem). 一个图不是平面图等价于图包含一个和
edge-equivalent的子图。
Polyhedra
多面体由多边形组成了边界。生活中多面体是非常常见的，比如立方体、四面体和棱柱。
多面体有一些很好的性质，这些性质是平面图所没有的。最重要地，所有的面至少有三条边，所有的点至少被三个面共有。多面体至少要有四个面，四个顶点和六条边。
几何学中，如果多面体绝对对称，称之为正多面体(regular)，所有的面有同样数量的边，所有点被相同数量，，的边所包含（这里的是多面体中的度），所有边有同样的长度，每个面的每个角的度数都一样。比如立方体是一个正多边形。组合数学中，我们忽略边的长度和角度。你可以想象是三维世界的正多边形就是二维世界的正多边形。
不过正多边形和正多面体有一个很大的不同。对于所有整数，个顶点的正多边形都存在，也就是正多边形是无穷多的，但是正多面体是有限的，这个小节会证明只有五种不同的正多面体。
其中一个有用的工具是Euler's Theorem，它对凸多面体也是成立的。从Theorem 12.2可以证明。本质上，多面体就是平面图，准确地说，边和点的集合从平面图而来。平面图被称为多面体的1-skeleton。
这里我们给出Euler's Theorem的另外一个证明。证明简介，不需要递归和树的性质。证明过程涉及的很多东西都很有用。
Theorem 12.6. 是个顶点、个面和条边的凸多面体，那么。
Proof. 假设是一个和各个面都不垂直的平面，将投影到上得到投影图。由于是凸多面体，每个条边的面的投影是凸边形。我们用两种方法来计算所有面（的边界也是一个面）的角度之和。
第一种方法是从顶点的角度出发。假设上有个顶点，内部有个顶点，那么。
内部个点，每个点的角度是360，角度总数是。的边界是凸边形，内角和是，由于每个这些角不同的面用两次（边界这个面和与边界相邻的面），所以要计算两次，那么
另一方面，如果有个凸边形，它的内角和是。的个面的边数分别是，由于每条边被两个面共享，那么
从边的角度出发，角度之和是
对比公式，得到。
对于所有的，有公式。的左边至少是，所有可以得到如下推论。
Corollary 12.7. 对于任意有个面和条边的凸多面体，都有。
类似的，可以证明一个关于凸多面体中点的个数和边的个数的关系的定理。
Proposition 12.8. 对于任意有个顶点和条边的凸多面体，都有。
Proof. 令表示每个点的度，由于每个边包含两个顶点，那么
对于任意顶点，度至少是3，即对于所有的，都有，那么左边至少是。
上面展示了面和边、点和边之间的简单的关系，那么面和点之间有类似的简单的关系吗？然而这不简单，因为上面的推理过程都用了一个性质：每条边被两个面共有，包含两个顶点。面和点之间没有这样一致的性质。
我们现在有使用点的数量和面的数量来表示的边的数量的下界，那么上界呢？一个个顶点的简单图，一直加边，直至形成图，对于而言，不是平面图。我们的目标是要找到上界，即多少边就会太多了。
Lemma 12.9. 在任意凸多面体中，有。
Proof. 从Corollary 12.7可知，代入Euler's theorem得到
从Proposition 12.8可知，同理可证第二个公式。
在上面一系列的证明中，和是对称的。有一个深层次、结构化的原因，后续会解释，先来看看一些有些出人意料的事情。
Lemma 12.10. 所有的凸多面体至少有一个面至少有五条边。
Proof. 从Lemma 12.9可知，代入公式得到
因此，不能对于所有都有，否则。
类似的，下面这个就显得稀松平常了。
Lemma 12.11. 所有的凸多面体至少有一个顶点至少有五条边。
Proof. 从Lemma 12.9可知，代入公式得到
因此，不能对于所有都有，否则。
Lemma 12.9对所有平面图都成立，不仅仅是多面体。Exercise 12是个机会来证明这一点。
Lemma 12.10和Lemma 12.11对于寻找所有的正多面体是有用的。每个点的度不能等于6，那么只有3，4，5三种可能，同理，面也是这样。那么只有三三得九种情况需要分析。
令是平面图，下面的步骤来构造图。的面中间点是的顶点。的两个顶点中用条边连接如果在中所在的面有个公共边，且公共边被一条间的边穿过。这个过程在的面和的顶点之间构造了双射，同时在这两个图的边之间构造了双射。因此如果有条边、个顶点和个面，那么也有条边，但又个顶点和个面。也是平面图。下图是一个例子。
Definition 12.12. 上述定义的图被称为平面图的对偶图。
凸多面体的对偶还是图多面体，正多面体的对偶还是正多面体。
如果一个定理对多面体在参数和上成立的话，那么对多面体也成立，后者的参数是面数和边数。
现在，我们找所有的正多面体。前面说过度只能是3，4，5。在正多面体中，所有面都有条边，那么代入
(A) ，那么对于所有都有，通过公式可以得到。代入Euler's Theorem得到，将代入得到
那么只能是以下三种情况
(a) ，那么，正四面体。
(b) ，那么，立方体。
(c) ，那么。有12个面，每个面是正五边形。上下各方一个五边形，然后对于每个边，再拼接一个五边形，上下两个部分组成要给整体，即正十二面体。
(B) ，通过得到，那么。联合，
的唯一可能的正整数解是，那么。这个正多边形是立方体的对偶 - 正八面体。
(C) ，通过得到，那么。联合，
的唯一可能的正整数解也是，那么。正十二面体的对偶恰好是这个正多面体 - 正二十面体。
讨论完所有的可能性就得到下面的定理：
Theorem 12.13. 有五种正多边形：正四面体、立方体、正十二面体、正八面体和正二十面体。
Coloring Maps
世界地图对于邻国使用不同的颜色染色，否则，就看不出来边界在哪里了。
这个问题是数学中很有名的问题。对于任意地图，对其进行染色，相邻国家不能用同样的颜色，最后要求颜色的种类越少越好。不管地图是什么样的，这个最小值是多少呢？
从图论的角度看，所有地图都是平面图。我们需要找到合适的颜色来对面进行染色，有相同边的面需要用不同的颜色，有相同的点的面可以使用相同的颜色。根据对偶性，这个问题等价于用多少中颜色给平面图的顶点染色，要求邻接点不能是同一种颜色。
因为是平面图，最少使用四种颜色。尝试一些所有国家都是连续相邻的（能从一个国家的任一点到另外一点，而不需要跨过其他国家。美国就不是连续相邻的，因为你不能从阿拉斯加到加州而不经过加拿大）地图，四种颜色足够了。这个问题被称为四色猜想(Four-Color Conjecture)。
对于热身，我们从最少需要六种颜色开始。为了方便起见，采用对偶的给顶点染色的方式证明。
Proposition 12.14. 任意平面图的顶点能够被六种颜色染色。
Proof. 基于递归。当时，显然成立。假设对于成立，考虑的情况。Exercise 12（Lemma12.11对于简单平面图的泛化）告诉我们至少有一个顶点的度最多是五。从中移除，得到，根据递归，由六种颜色染色，那么只和五个顶点相交，显然可以用第六种颜色染色。
根据对偶性，所有的地图都能被六种颜色染色。下面考虑稍难一些的问题：五种颜色对任意平面图染色。
Theorem 12.15. 任意平面图的顶点能够被五种颜色染色。
Proof. 和上面的证明类似。我们顺时针标记的邻接点分别是，颜色分别是。如果和同色，证毕。如果不同色，说明这两点之间有一条路径，交替染成了的颜色，和同理。这就出现了矛盾的地方，路径和相交。如下图所示。
根据对偶性，所有的地图都能被五种颜色染色。
Exercises
(4) 证明对于任意多面体，总存在两个相邻顶点有同样的边数。
Proof. 假设没有这样的顶点，那么每个顶点的边数都是不同的，也就是个顶点的边数的两倍至少是。结合Lemma 12.9，得到
但是根据二项式性质，对于任意整数，矛盾，所以假设不成立。
(6) 不使用Euler's Theorem及其推论，证明所有的多边形有两个面有相同的顶点数。
Proof. 多面体的各个面，最多有条边（也就是个顶点），令有条边，每条边对应一个面，共有个面。这个面最多有条边，最少有3条边，根据鸽巢原理，至少有两个面的边数一样多。