二、平面图的特征找出一个图是平面图的充分必要条件的研究曾经持续了几十年，直到1930年库拉托斯基(Kuratowski)给出了平面图的一个非常简洁的特征
二、平面图的特征 找出一个图是平面图的充分必要条件的 研究曾经持续了几十年, 直到 1930 年库 拉托斯基 (Kuratowski) 给出了平面图的 一个非常简洁的特征
首先介绍部分的概念：给定图G的一个部分是对G实行有限次下述过程而得到的图：删去它的一条边{u,v后添加一个新的点w以及新的边w,u和w,也就是说在G的边上插入有限个点便得到G的一个部分。下图中给出了K的一个部分
首先介绍剖分的概念： 给定图G的一个剖分是对G实行有限次下 述过程而得到的图: 删去它的一条边{u,v}后添加一个新的点 w以及新的边{w,u}和{w,v}。 也就是说在G的边上插入有限个点便得 到 G的一个剖分。 下图中给出了K5的一个剖分
定理：（1)若图G的一个子图是K,的分，则G中至少有n个顶点度数大于等于n-1；(2)若图G的一个子图是K，,的剖分，则G中至少有2n个顶点度数大于等于n。 例：G=(V,E)，IV=7，若G中含有K,的剖分，则G不含有K或K3的部分定理6.3（库拉托斯基定理）：图G是平面图当且仅当它的任何子图都不是K,或K3,3的部分。上例中G是非平面图，而G是平面图
定理：(1)若图G的一个子图是Kn的剖分， 则G中至少有n个顶点度数大于等于n-1； (2)若图G的一个子图是Kn,n的剖分，则G 中至少有2n个顶点度数大于等于n。 例：G=(V,E)，|V|=7，若G中含有K5的剖 分，则 不含有K5或K3,3的剖分. 定理 6.3 (库拉托斯基定理):图G是平面图 当且仅当它的任何子图都不是K5或 K3,3 的剖分。 上例中G是非平面图，而 是平面图 G G
此定理告诉我们：(1)一个图是平面图，则不含有K的剖分也不含有K的剖分。(2)若图G不含有K,的剖分，也不含有K3,3的剖分。则G一定是平面图。(3)若图G含有K的剖分，则G一定不是平面图；若图G含有K3的剖分，则G一定不是平面图。（4)若图G不是平面图，则或者G含有K的剖分，或者G含有K33的剖分
此定理告诉我们： (1)一个图是平面图，则不含有K5的剖分， 也不含有K3,3的剖分。 (2)若图G不含有K5的剖分，也不含有K3,3 的剖分。则G一定是平面图。 (3)若图G含有K5的剖分，则G一定不是 平面图；若图G含有K3,3的剖分，则G一 定不是平面图。 (4)若图G不是平面图，则或者G含有K5 的剖分，或者G含有K3,3的剖分