《集合论与图论》课堂练习3
（2011年12月 复旦大学计算机学院10级）
学号 姓名
1．证明：任何平面图是5-可着色的。 证明：
2．证明：n个顶点的简单图G的边数超过(n-1)(n-2)/2条边，则G是连通的。 证明：
3．证明：马在国际象棋3?4的棋盘上可以遍历。 证明：
4．如果一个带有e条边和n个顶点的连通简单平面图不包含长度为4或更短的回路。证明：若n?4，则e?（5/3）n-（10/3）。
5 用下述算法为简单图着色：
（1） 以度数递减的顺序给出顶点的列表v1, v2, …, vn，使得d(v1)?d(v2)? …d(vn)； （2） 把颜色1着色给顶点v1和在列表中不与顶点v1相邻的下一个顶点（若存
在一个这样的顶点），并且继续给列表中每一个不与着颜色1 的顶点相邻的顶点着颜色1；然后，把颜色2 着色给列表中还没有着色的第一个顶点，并继续按上述步骤对列表中的顶点着颜色2；然后，以此类推，直到所有的顶点都被着色。
举例说明这一算法不是最优的，也就是说，这个算法所产生的着色所需的颜色数可能比某个图的色数大。
6 简单图的定向就是指定它的各边的方向，使得所得的图是强连通图。证明：若一个图有割边，则它不是可定向的。
