概念

定义一

设G是一个平面图，通过删除G的一条边(x，y)，并且添加一个新结点a和两条边(x,a)与(a,y)(所获得的任何图也是平面图)。这样的操作称为初等细分。若可以从相同的图G通过一系列初等细分来获得图G₁和G₂，称G₁和G₂是同胚的(homeomorphism)。

如图1、2、3所示的三个图G₁、G₂和G₃都是同胚的。2

定义二

设G=(V，E)是一个图，e=uv是图G的一条边，w不是G的顶点，则当增加二度点w且用uw和vw代替边e时，就称边e被细分．若图H是由G经过一系列边的细分而得到，则称H为图G的剖分图(或细分图)．若两个图都是某一个图的剖分图，则这两个图称为同胚的(或二度顶点内同胚)．简单图G收缩边wuv是将G的边uv去掉，并将顶点u和v合并成一个新顶点．图G可收缩成图H．是指G可经过一系列的边收缩而变成H．如果H是G的剖分图，则G一定是H通过收缩一系列2度点所得到的收缩图．3

相关定理Kuratowski定理 图G是可平面的，当且仅当 和 的任何细分图都不是G的子图。

根据对细分图的描述，我们知道不仅 和 是不允许作为子图出现的，而且它们的任何边细分图也是不允许的子图，记住这一点很重要：违禁子图不应被归纳出来。如果它们的确出现了，G就是不可平面的。4

例题例1 证明Peterson图是不可平面的。4

证明 我们首先尝试使用定理“如果G是n结点(n≥3)q边的可平面图，则q≤3n一6”。Peterson图有q=15条边和n=10个结点。代入定理中的不等式，我们得到15≤3(10)-6=24。非常遗憾，这条定理不起作用。满足这个不等式并不能保证其可平面性，但是如果Peterson图没能满足这个不等式，我们就能得出它是不可平面的。所以我们得换用另一个工具——"图G是可平面的，当且仅当 和 的任何细分图都不是G的子图"。由于 的任何细分图都有度为4的结点，且Peterson图是3一正则图，所以我们只需要寻找 的细分图。图4(a)是有标记Peterson图，(b)是它的子图同时也是 的细分图，我们将这个子图重画为(c)以澄清它确实是 的子图。因此，根据定理，Peterson图的确是不可平面图。4

例2 用Kuratowski定理说明图5所示图G不是平面图。

解 将从图G中找出一个同胚于 的子图。图G中结点a、b、f和e的度数均为4．删去G中边(a，b)与(f，e)得到图G的一个子图 ，且 中每个结点的度数均为3。再删去图 中边(g，h)得到图 ，图 当然是图G的子图，且图 中有两个2度结点g与f，而图 同胚于 ，因此图G不是平面图。2