(1) 而每个面至少由3条边围成，有3r≤2m，则r≤2m/3，因r是整数,故r≤４。 又对任意得顶点v∈V，degv≥3，有3n≤2m，故n≤2m/3，因为n是整数， 故n≤４。所以n+r≤４＋４=８与（１）矛盾，所以结论正确。
37、设G是一个没有三角形的平面图，则
（1）证明：G中存在一个顶点v，使得degv≤3； （2）证明：G是4-可着色的。
38、设树T中有2n个度为1的顶点,有3n个度为2的顶点,有n个度为3的顶点,则这棵树T有几个顶点和几条边？
39、设T是一棵树且△(T)≥k,证明:T中至少有k个度为1的顶点。
40、设G是一个(p,q)图, 若q≥p,证明G中必有圈。 41、证明:任一非平凡树最长路的两个端点都是树叶。(任一非平凡树中至少有两个度为1的顶点。)
42、证明:恰有两个顶点度数为1的树必为一条通路。
43、设T=(V,A)是一个有根树,其每个顶点的出度不是0就是2。若T有n0个叶子，试求T的弧的条数。
44、设T=(V,A)是一个正则二元树,若T有n0个叶子，试求的弧的条数。
45、设T是有n0个叶子的正则二元树，n2个出度为2的顶点，证明：n0=n2+1。
6
46、设T是有n0个叶子的二元树，出度为2的顶点为n2，证明：n0=n2+1。
47、设T是一个有p个顶点的正则二元树，求T的叶子数，其中p奇数。
48、证明：任一棵正则(满)二元树必有奇数个顶点。
49、菱形12面体的表面上有无哈密顿回路？
50、设G=(V,E)是连通图且顶点数为p,最小度数为δ，若p>2δ,则G中有一长至少为2δ的路。
51、设G=(V,E)是p(p>3)个顶点的简单无向图,设G中最长路L的长度为l(l≥2)，起点与终点分别为u,v，而且degu+degv≥p。证明：G中必有与L不完全相同但长度也为L的路。
52、已知a,b,c,d,e,f,g7个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？
53、设G为p个顶点的简单无向图。则
(1) 若G的边数q= (p-1)·(p-2)/2+2，证明G为哈密顿图。
(2) 若G的边数q= (p-1)·(p-2)/2+1，则G是否一定为哈密顿图？
7
54、已知9个人v1,v2,…,v9，其中v1和两个人握过手，v2,v3,v4,v5各和3个人握过手，v6和4个人握过手，v7,v8各和5个人握过手，v9和6个人握过手。证明:这9个人中一定可以找出3个人互相握过手。
55、(1)一棵无向树有ni个度数为i的顶点,i=1,2,…,k。n2,n3,….nk均为已知数，问n1应为多少？
(2)在(1)中，若nr(3≤r≤k)未知，nj(j≠r)均为已知数，问nr应为多少？
56、设G是平面连通图，顶点为p面数f，证明:
(1)若p≥3，则f≤2p-4。(2)若δ(G)=4,则G中至少有6个顶点的度数≤5。 57、设d=(d1,d2,…,dn),其中di为非负整数，i=1,2,…,n。若存在n个顶点的(简单)无向图,使得顶点vi的度为di，则称d是可图解的。下面给出的各序列中哪些是可图解的？哪些不是，为什么？ （1）（1,1,1,2,3）； （6）（1,3,3,3）； （2）（0,1,1,2,3,3）；（7）（2,3,3,4,5,6）； （3）（3,3,3,3）； （8）（1,3,3,4,5,6,6）； （4）（2,3,3,4,4,5）；（9）（2,2,4）； （5）（2,3,4,4,5）； （10）(1,2,2,3,4,5）。
58、设G是有个p顶点，q条边的无向图，各顶点的度数均为3。则 (1)若q=3p-6,证明:G在同构意义下唯一，并求p,q。 (2)若p=6，证明:G在同构的意义下不唯一。
59、已知p阶(简单)无向图中有q条边，各顶点的度数 均为3，又2p=q+3，试画出满足条件的所有不同 构的G。
60、证明：在一个连通图中，两条最长的路有一个公共的顶点。
8
61、若G是一个恰有两个奇度顶点u和v的无向图，则 G连通?G+uv连通。
62、证明：若无向图G是不连通的，则G的补图GC是连通的。（逆命题不成立）
63、某工厂生产由6种不同颜色的纱织成的双色布。双色布中，每一种颜色至少和其他3种颜色搭配。证明:可以挑出3种不同的双色布,它们含有所有6种颜色。
64、设G是一个有p(p≥3)个顶点的连通图。u和v是G的两个不邻接的顶点,并且degu+degv≥p。证明：G是哈密顿图?G+uv是哈密顿图。
65、证明：完全图K9中至少存在彼此无公共边的两条哈密顿圈和一条哈密顿路？
66、把平面分成p个区域，每两个区域都相邻，问p最大为多少？
67、证明：不存在具有5个面，每两个面都共享一条公共边的平面图G。
68、设T为任一棵正则二元树，q为边数，n0为树叶数，证明：q=2n0-2。其中n0≥2。
69、设图G中有9个顶点，每个顶点的度不是5就是6。证明:G中至少有5个6度顶点或至少有6个5度顶点。
70、将无向完全图K6的边随意地涂上红色或绿色,证明:无论何种涂法,总有红色的K3
9
或绿色K3。
71、给无向完全图Kp(p≥7)的各边随意地涂上红色或绿色，若已知从某点v0引出的p-1条边中至少有6条边涂红色，则Kp存在红色的K4或绿色的K3。
72、有17位学者，每2位讨论3篇论文中的一篇且仅一篇，证明：至少有3位学者，他们相互讨论的是同一篇论文。
p
d i ?73、设d1,d2,…,dp是p个正整数,p≥2,且 2 p ? 2 。
证明:存在一棵顶点度数为d1,d2,…,dp的树。 i?1
74、判断下面命题是否正确，并说明理由。
任意平面图G的对偶图G*的对偶图G**与G同构。
75、设G*是平面图G的对偶图，证明：p*=f，q*=q， f*=p-k+1。其中k(k≥1)为G的连通分支数。
76、证明：若G是自对偶的平面图，则q=2p-2。其中p和q是G的边与顶点数。
定义、定理及推论：
1、对于“5”这个数。世界上有“5”这个事物吗？没有。有的只是具体的5个事物，如5个人，5只笔，5张桌子等等，而这个“5”无非就是一个符号，它表明具有5个事物所形成的集合的共性。它们的共性就是它们相互对等，即它们的元素之间可以建立起一一对应。于是， “5”这个符号就是赋给每个含有五个元素的集合的一个记号，即若与含有五个元素的集对等，则都赋以相同的记号“5”。实际上，这就是“5”的本质。
2、设X，Y，Z为三个非空集合。一个从X×Y到Z的映射称为X与Y到Z的一个二
? 10