定理:设G是极大平面图,有n(3)个结点,m条边 则mF=3n6 证明:设G有r个面。由于极大平面图是连通图 所以G是连通图。由欧拉公式得r=2+mn,又因为G是 极大平面图,G的每个面的次数均为3,所以2m= ∑deg()=3r=3(2+mn)。整理后,m=3n6。 定理:设G是简单平面图,则G的最小度8≤5 证明:设G有n个结点,m条边。当6,因为G是 简单图,因此,δ(G≤A(G≤5。以下证≥7的情况, 若8()≥6,即每个结点的度数大于等于6,G中所有结 点度数之和大于等于6n。于是2m=∑degm) ≥6n,m≥3n>3n6,即m>3n6,矛盾。1
定理：设G是极大平面图，有n(n≥3)个结点，m条边， 则m=3n–6。 证明：设G有r个面。由于极大平面图是连通图， 所以G是连通图。由欧拉公式得r=2+m-n，又因为G是 极大平面图，G的每个面的次数均为3，所以2m= =3r=3(2+m-n)。整理后， m=3n–6。 定理： 设G是简单平面图，则G的最小度(G)≤5。 证明：设G有n个结点，m条边。当n≤6，因为G是 简单图，因此， (G)≤(G)≤5。以下证n≥7的情况， 若(G)≥6，即每个结点的度数大于等于6，G中所有结 点度数之和大于等于6n。于是 2m= ≥6n，m≥3n＞3n–6，即m＞3n–6，矛盾。 deg( ) 1 = r i i r deg( ) 1 = n i i v
库拉图斯基定理 设G是一个平面图,通过除G的一条边{xy},并 个新结点和两条边{x,与{(所获得的任何度 是平面图),这样的操作称为初等细分。若可以从 同的图G通过一系列初等细分来获得图G1和G2,称G1 和G2是同胚的。 如下图G1G2G3是同胚的
库拉图斯基定理 设G是一个平面图，通过除G的一条边{x,y},并增加 一个新结点a和两条边{x,a}与{a,y}（所获得的任何图也 是平面图），这样的操作称为初等细分。若可以从相 同的图G通过一系列初等细分来获得图G1和G2，称G1 和G2是同胚的。 如下图G1 ,G2 ,G3是同胚的。 G1 G2 G3