HMMT 二月 2009 · TEAM1 赛 · 第 4 题

HMMT February 2009 — TEAM1 Round — Problem 4

A k-clique of a graph is a set of k vertices such that all pairs of vertices in the clique are adjacent. (a) [ 6 ] Find a graph with chromatic number 3 that does not contain any 3-cliques. Page 1 of 2 (b) [ 10 ] Prove that, for all n > 3, there exists a graph with chromatic number n that does not contain any n -cliques.

解析

A k-clique of a graph is a set of k vertices such that all pairs of vertices in the clique are adjacent. (a) [ 4 ] Find a graph with chromatic number 3 that does not contain any 3-cliques. Solution: Consider a graph with 5 vertices arranged in a circle, with each vertex connected to its two neighbors. If only two colors are used, it is impossible to alternate colors to avoid using the same color on two adjacent vertices, so the chromatic number is 3. (b) [ 10 ] Prove that, for all n > 3, there exists a graph with chromatic number n that does not contain any n -cliques. Solution: We prove the claim by induction on n . The case n = 3 was adressed in (a). Let n ≥ 3 and suppose G is a graph with chromatic number n containing no n -cliques. ′ We produce a graph G with chromatic number n + 1 containing no ( n + 1)-cliques as follows. Add a vertex v to G , and add an edge from v to each vertex of G . To see this graph has chromatic number n + 1, observe that any coloring of the vertices ′ of G restricts to a valid coloring of the vertices of G . So at least n distinct colors must be used among the vertices of G . In addition, another color must be used for v . By ′ coloring v a new color, we have constructed a coloring of G having n + 1 colors. ′ Lastly, any ( n +1)-clique in G must have at least n vertices in G which form an n -clique, ′ which is impossible. Therefore, G has no ( n + 1)-cliques.