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