2. 若G是顶点数p≥11的平面图，试证Gc不是平面图。
4．证明：不存在7条棱的凸多面体。
14. 图G的最短圈的长度称为G的围长；若G中无圈，则定义G的围长为无穷大。 (1)证明：围长为r的平面连通图G中有q≤r(p-2)/(r-2)，r≥3 (2)利用(1)证明Petersen图(见图3.6.4)不是平面图。
31
P294习题
1.设G是一个没有三角形的平面图。应用欧拉公式证明G中有一个顶点v，使得degv ≤3。
2.设G是一个没有三角形的平面图。应用数学归纳法证明G是4－可着色的(事实上，可以证明G是3－可着色的)。
第十章 有向图
P301习题
2.画出具有三个顶点的所有互不同构的有向图的图解。
3.具有p个顶点的完全有向图中有多少条弧？
32
P307习题
1.设D是一个有p个顶点q条弧的有向图。若D是连通的，证明：p-1≤q≤p(p-1)。
2.设D是一个有p个顶点q条弧的强连通的有向图，则q至少是多大？
4.证明：有向图D是单向连通的当且仅当D有一条生成通道。
P307习题
2.有向图D的图解如图10.4.3所示 (1)写出D的邻接矩阵及可达矩阵； (2)写出D关联矩阵。
33
3.设D为图10.4.4中的有向图，试求v2到其余每个顶点的长≤4的所有通道的条数。
4.已知有向图D的邻接矩阵B，如何从B求D的可达矩阵R？
P321习题
1.设T是一个正则m元有序树，它有n0个叶子，T有多有多少条弧？
3.设T是一个有n0个叶子的二元树，出度为2的顶点为n2，试证：n0=n2+1。
4.具有三个顶点的有序树共有多少个？具有三个顶点的有根树有多个？注意，同构的只算一个。
8. 用数学归纳法证明每个比赛图中必有有向哈密顿路。
34