5.设无向树T有3个3度,2个2度结点, 其余结点都是树叶,问T有几片树叶? 握手定理
5. 设无向树T有3个3度，2个2度结点， 其余结点都是树叶，问T有几片树叶？ 握手定理
6.证明:在任何两个或两个以上人的组 内,存在两个人在组内有相同个数的朋 友 /*等价于:至少有两个顶点的筒单图有两个相 同度数的顶点 中国和学能自动化所1998考研
6. 证明：在任何两个或两个以上人的组 内，存在两个人在组内有相同个数的朋 友。 /*等价于：至少有两个顶点的简单图有两个相 同度数的顶点 /*中国科学院自动化所1998考研
二、平面图、欧拉公式的应用 1,关于平面图的不等式的证明 欧拉公式及其推论的运用 2,非平面图的判定 应用库拉托斯基定理
二、平面图、欧拉公式的应用 1，关于平面图的不等式的证明 欧拉公式及其推论的运用 2，非平面图的判定 应用库拉托斯基定理
1.设G是n个结点的连通简单平面图,若 n3,则G中必有一个结点度数不超过5。 ■提示:涉及度数,握手定理;连通平面 图,欧拉公式;简单平面图,若n≥3,欧 拉公式的推论 (西南交大1999考研)
1. 设G是n个结点的连通简单平面图，若 n3，则G中必有一个结点度数不超过5。 提示：涉及度数，握手定理；连通平面 图，欧拉公式；简单平面图，若n3，欧 拉公式的推论 （西南交大1999考研）
■证明: 握手定理:∑dev(v;)=2e; 反证:设每个结点的度数超过5,即 dev(v;)≥6,则2e=∑dev(v:)≥6n,所以 e≥3n 由欧拉公式的推论,e≤3n-6。 所以矛盾
证明： 握手定理：dev(vi)=2e; 反证：设每个结点的度数超过5，即 dev(vi)6，则2e=dev(vi)6n, 所以 e3n. 由欧拉公式的推论，e3n-6。 所以矛盾