极大平面图 1、定义 定叼8若在简单平面图G中的任意两个不相邻的顶点之 间加一条新边所得图为非平面图,则称G为极大平面图。 胜意8若简单平面图G中已无不相邻顶点,G显然是极大平 面图,如K1(平凡图),K2,K3,K4都是极大平面图。 、极大平面图的主要性质 定76极大平面图是连通的。 定叫6n13阶极大平面图中不可能有割点和桥
三、极大平面图 1、 定义 定义17.3 若在简单平面图G中的任意两个不相邻的顶点之 间加一条新边所得图为非平面图，则称G为极大平面图。 注意：若简单平面图G中已无不相邻顶点，G显然是极大平 面图，如K1（平凡图）,K2 , K3 , K4都是极大平面图。 2、极大平面图的主要性质 定理17.5 极大平面图是连通的。 定理17.6 n(n3)阶极大平面图中不可能有割点和桥
定理叫7设G为n(n≥3))阶简单连通的平面图,G为极大平面图 当且仅当G的每个面的次数均为3 明思 口本节只证明必要性,即设G为n(n≥3))阶简单连通的平面图,G 为极大平面图,则G的每个面的次数均为3。 口由于n≥3,又G必为简单平面图,可知,G每个面的次数均≥3。 口因为G为平面图,又为极大平面图。可证G不可能存在次数>3 的面
定理17.7 设G为n(n3) )阶简单连通的平面图，G为极大平面图 当且仅当G的每个面的次数均为3。 ❑本节只证明必要性，即设G为n(n3) )阶简单连通的平面图，G 为极大平面图，则G的每个面的次数均为3。 ❑由于n3, 又G必为简单平面图，可知，G每个面的次数均3。 ❑因为G为平面图，又为极大平面图。可证G不可能存在次数>3 的面。 证 明 思 路
假设存在面R的次数deg(R)=≥4, 如图所示 在G中,若v与v3不相邻,在R内加边(v1,"3不破坏平面性,这 与G是极大平面图矛盾,因而v与v3必相邻,由于R的存在, 边(v13)必在R外。 类似地,"2与v也必相邻,且边(2,4也必在R外部,于是必 产生(v,"3)与(2”)相交于R的外部,这又矛盾于G是平面图, 所以必有s=3,即G中不存在次数大于或等于4的面,所以G的 每个面为3条边所围,也就是各面次数均为3
假设存在面Ri的次数deg(Ri )=s≥4， 如图所示。 在G中，若v1与v3不相邻，在Ri内加边(v1 ,v3 )不破坏平面性，这 与G是极大平面图矛盾，因而v1与v3必相邻，由于Ri的存在， 边(v1 ,v3 )必在Ri外。 类似地，v2与v4也必相邻，且边(v2 ,v4 )也必在Ri外部，于是必 产生(v1 ,v3 )与(v2 ,v4 )相交于Ri的外部，这又矛盾于G是平面图， 所以必有s＝3，即G中不存在次数大于或等于4的面，所以G的 每个面为3条边所围，也就是各面次数均为3。 s S-1
只有右边的图为极大平面图 因为只有该图每个面的次数都为3
只有右边的图为极大平面图。 因为只有该图每个面的次数都为3
四、极小非平面图 定叼4若在非平面图G中任意删除一条边,所得图G为平面 图,则称G为极小非平面图。 由定义不难看出: 口Ks,K3都是极小非平面图 口极小非平面图必为简单图。 例四8以下各图均为极小非平面图。 小节结京
四、极小非平面图 定义17.4 若在非平面图G中任意删除一条边，所得图G为平面 图，则称G为极小非平面图。 由定义不难看出： ❑ K5 , K3,3都是极小非平面图。 ❑ 极小非平面图必为简单图。 例如：以下各图均为极小非平面图。 小节结束