514(1)若简单图G至多有2n个顶点每 个顶点度数至少为n,则G是连通图。(2)若 简单图G至多有2n个顶点每个顶点度数 至少为n-1,则G是连通图?为什么? 不一定 1517证明:对于任何简单图G,或者G是连 通的或者KG是连通的。 1521若G是一个多于四个顶点的任意简 单图,则或者G或者KG包含一条回路
[5.14](1)若简单图G至多有2n个顶点,每 个顶点度数至少为n,则G是连通图。(2)若 简单图G至多有2n个顶点,每个顶点度数 至少为n-1,则G是连通图? 为什么? 不一定 [5.17]证明:对于任何简单图G,或者G是连 通的或者K-G是连通的。 [5.21]若G是一个多于四个顶点的任意简 单图, 则或者G或者K-G包含一条回路
529](1)完全图Kn是欧拉图吗?是哈密 顿图吗? (2)完全二分图是欧拉图吗?是哈密顿图 吗
[5.29](1)完全图Kn是欧拉图吗? 是哈密 顿图吗? (2)完全二分图是欧拉图吗? 是哈密顿图 吗?
167设连通平面图G的顶点度数至少为3, 且其面数f12证明G有一个面的边数小 于5 68设图G的顶点度数至少为3,且面数 f12,则G是4面可着色的。 612设G是简单图,有n个顶点1)证明: 若n<8,则G与中至少有一个是平面图;
[6.7]设连通平面图G的顶点度数至少为3 , 且其面数 f<12,证明G有一个面的边数小 于5。 6.8 设图G的顶点度数至少为3，且面数 f<12，则G是4-面可着色的。 6.12 设G是简单图，有n个顶点(1) 证明： 若n<8，则G与中至少有一个是平面图；
6.14:求x(G)和x(G)
6.14:求(G)和*(G)
74(1)一棵树有两个顶点度数为2,一个 顶点度数为3,三个顶点度数为4问它有几 个度数为1的顶点? 有几个度数为1的顶点k问它 (2)一棵树有n个顶点度数为 (3)设n是树中度数为顶点数。证明: n1≥n;,(i=2,3,,△),或者 n2>n1≥n(i=3,4,…,△)
[7.4](1)一棵树有两个顶点度数为2, 一个 顶点度数为3,三个顶点度数为4,问它有几 个度数为 1 的顶点? (2)一棵树有ni个顶点度数为i,2ik,问它 有几个度数为 1的顶点? (3)设ni是树中度数为i的顶点数。证明: n1ni ,(i=2,3,…,),或者 n2>n1ni (i=3,4, …,)