◆由此定理我们可以证明K是非平面图, ◆因为K是连通的, ◆n=5,e=10, ◆若K是平面图,则由推论应该有es3n-6 ◆即10≤3*5-6=9, ◆矛盾,所以K不是平面图。 在这里要注意:对于n≥3的平面简单图, 定成立e≤3n-6。 ◆若e>3n-6,则一定不是平面图。 ◆但对于简单图,即使满足e≤3n-6,也不一定 是平面图。 ◆例如,K3,m=6e-9,3n6=36-6=12>9=e, 成立,但K3不是平面图
由此定理我们可以证明K5是非平面图, 因为K5是连通的， n=5,e=10， 若K5是平面图，则由推论应该有e3n-6 即103*5-6=9, 矛盾，所以K5不是平面图。 在这里要注意：对于n3的平面简单图, 一 定成立e3n-6。 若e>3n-6,则一定不是平面图。 但对于简单图，即使满足e3n-6，也不一定 是平面图。 例如，K3,3，n=6,e=9, 3n-6=3*6-6=12>9=e， 成立，但K3,3不是平面图
◆推论6:若平面图的每个面由四条或更 多条边围成,则e≤2n-4 ◆证明:因为每个面由四条或更多条边围 成,因此边的总数s大于或等于4f;即 s≥4f ◆证明K3不是平面图
推论 6.2：若平面图的每个面由四条或更 多条边围成, 则e2n-4 证明：因为每个面由四条或更多条边围 成，因此边的总数s大于或等于4f，即 s4f 证明K3,3不是平面图
定理62:在平面简单图G中至少存在一个顶 点wo,使得d(vo≤5 证明:用反证法证明。 假设一个平面简单图的所有顶点度数大于5。 即d(v)≥6。 又由欧拉公式推论61有3n6≥e, 所以6n-12≥2e=∑()26n 这是不可能的。 因此平面简单图中至少有一个顶点v,它的度 数d(vo)≤5
定理 6.2:在平面简单图 G 中至少存在一个顶 点 v0,使得 d(v0 ) 5。 证明：用反证法证明。 假设一个平面简单图的所有顶点度数大于 5。 即 d(v)6。 又由欧拉公式推论 6.1 有 3n-6e, 所以 6n-122e= d v n v V ( ) 6 这是不可能的。 因此平面简单图中至少有一个顶点 v0,它的度 数 d(v0 )5
例:小于30条边的连通平面简单图中存 在顶点度数不超过4的顶点。 证明:若所有顶点度数都大于4,即G中 所有顶点度数都≥5
例：小于30条边的连通平面简单图中存 在顶点度数不超过4的顶点。 证明：若所有顶点度数都大于4，即G中 所有顶点度数都5
◆二、平面图的特征 ◆找出一个图是平面图的充分必要条件的 研究曾经持续了几十年,直到1930年库 拉托斯基( Kuratowski)给出了平面图的 一个非常简洁的特征
二、平面图的特征 找出一个图是平面图的充分必要条件的 研究曾经持续了几十年, 直到 1930 年库 拉托斯基 (Kuratowski) 给出了平面图的 一个非常简洁的特征