HMMT 二月 2009 · TEAM2 赛 · 第 6 题
HMMT February 2009 — TEAM2 Round — Problem 6
题目详情
- (a) [ 5 ] If a single vertex is removed from a finite graph, show that the graph’s chromatic number cannot decrease by more than 1. (b) [ 15 ] Show that, for any n > 2, there are infinitely many graphs with chromatic number n such that removing any vertex from the graph decreases its chromatic number. Page 2 of 2
解析
- (a) [ 5 ] If a single vertex (and all its incident edges) is removed from a finite graph, show that the graph’s chromatic number cannot decrease by more than 1. Solution: Suppose the chromatic number of the graph was C , and removing a single vertex resulted in a graph with chromatic number at most C − 2. Then we can color the remaining graph with at most C − 2 colors. Replacing the vertex and its edges, we can then choose any color not already used to form a coloring of the original graph using at most C − 1 colors, contradicting the fact that C is the chromatic number of the graph. (b) [ 15 ] Show that, for any n > 2, there are infinitely many graphs with chromatic number n such that removing any vertex (and all its incident edges) from the graph decreases its chromatic number. Solution: Let k > 0 be an odd number, and let G be a graph with k vertices arranged in a circle, with each vertex connected to its two neighbors. If n = 3, these graphs can be arbitrarily large, and are the graphs we need. If n > 3, let H be a complete graph on n − 3 vertices, and let J be the graph created by adding an edge from every vertex in G to every vertex in H . Then n − 3 colors are needed to color H and another 3 are needed to color G , so n colors is both necessary and sufficient for a good coloring of J . Now, say a vertex is removed from J . There are two cases: If the vertex was removed from G , then the remaining vertices in G can be colored with 2 colors, because the cycle has been broken. A set of n − 3 different colors can be used to color H , so only n − 1 colors are needed to color the reduced graph. On the other hand, if the vertex was removed from H , then n − 4 colors are used to color H and 3 used to color G . So removing any vertex decreases the chromatic number of J . 2