5.下列说法正确的是( )
(A) 非平凡树和n(n?2)方体都是偶图； (B) 任何一个3正则图都可1-因子分解；
(C) 可1-因子分解的3正则图中一定存在哈密尔顿圈； (D) 平面图G的对偶图的对偶图与G是同构的。
三、 (10分)设无向图G有12条边，且度数为3的结点有6个，其余结点的度数小于3，求G的最少结点个数。
四，(12分) 在下面边赋权图中求：(1)每个顶点到点a的距离(只需要把距离结果标在相应顶点处，不需要写出过程); (2) 在该图中求出一棵最小生成树，并给出最小生成树权值(不需要中间过程，用波浪线在图中标出即可).
a 7 1 1 2 3 3 6 2 5 7 4 3 6 1 2 4
五．(10分) 今有赵、钱、孙、李、周五位教师，要承担语文、数学、物理、化学、英语五门课程。已知赵熟悉数学、物理、化学三门课程，钱熟悉语文、数学、物理、英语四门课程，孙、李、周都只熟悉数学、物理两门课程。问能否安排他们都只上他们熟悉的一门课程，使得每门课程都有人教（用图论方法求解）。
六．(6分)设l是赋权完全偶图G=(V,E)的可行顶点标号，若标号对应的相等子图Gl含完美匹配M*,则M*是G的最优匹配。
七.(6分) 求证：在n阶简单平面图G中有?(G)?5，这里?(G)是G的最小度。
八、(10分)课程安排问题：某大学数学系要为这个夏季安排课程表。所要开设的课程为：图论(GT), 统计学(S),线性代数(LA), 高等微积分(AC), 几何学(G), 和近世代数( MA )。现有10名学生(学生用Ai表示，如下所示）需要选修这些课程。根据这些信息，确定开设这些课程所需要的最少时间段数，使得学生选课不会发生冲突。 (要求用图论方法求解)
A1 : LA, S ; A2 : MA, LA, G ; A3: MA, G, LA ; A4: G, LA, AC ; A5: AC, LA, S ; A6: G, AC; A7: GT, MA, LA ; A8: LA,GT, S ; A9: AC, S, LA; A10: GT, S。
九．(9分)求下图G的色多项式Pk(G).
1 5 2 4 G
