HMMT 二月 2009 · TEAM1 赛 · 第 5 题
HMMT February 2009 — TEAM1 Round — Problem 5
题目详情
- The size of a finite graph is the number of vertices in the graph. (a) [ 15 ] Show that, for any n > 2, and any positive integer N , there are finite graphs with size at least N and with chromatic number n such that removing any vertex (and all its incident edges) from the graph decreases its chromatic number. (b) [ 15 ] Show that, for any positive integers n and r , there exists a positive integer N such that for any finite graph having size at least N and chromatic number equal to n , it is possible to remove r vertices (and all their incident edges) in such a way that the remaining vertices form a graph with chromatic number at least n − 1.
解析
- The size of a finite graph is the number of vertices in the graph. (a) [ 15 ] Show that, for any n > 2, and any positive integer N , there are finite graphs with size at least N and with chromatic number n such that removing any vertex (and all its incident edges) from the graph decreases its chromatic number. Solution: Let k > 1 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 2 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 . (b) [ 15 ] Show that, for any positive integers n and r , there exists a positive integer N such that for any finite graph having size at least N and chromatic number equal to n , it is possible to remove r vertices (and all their incident edges) in such a way that the remaining vertices form a graph with chromatic number at least n − 1. Solution: We claim that N = nr is large enough. Take a graph with at least nr vertices and chromatic number n , and take a good n -coloring of the graph. Then by Pigeonhole, at least r of the vertices are the same color, which means that no pair of these r vertices is adjacent. Remove this r vertices. If the resulting graph can be colored with only n − 2 colors, then we can add the r vertices back in and color them with a new ( n − 1)st color, creating a good coloring of the graph with only n − 1 colors. Since the original graph has chromatic number n , it must be impossible to color the smaller graph with n − 2 colors, so we have removed r vertices without decreasing the chromatic number by 2 or more.