HMMT 二月 2009 · TEAM1 赛 · 第 3 题

HMMT February 2009 — TEAM1 Round — Problem 3

A graph is finite if it has a finite number of vertices. (a) [ 6 ] Let G be a finite graph in which every vertex has degree k . Prove that the chromatic number of G is at most k + 1. (b) [ 10 ] In terms of n , what is the minimum number of edges a finite graph with chromatic number n could have? Prove your answer.

解析

A graph is finite if it has a finite number of vertices. (a) [ 6 ] Let G be a finite graph in which every vertex has degree k . Prove that the chromatic number of G is at most k + 1. Solution: We find a good coloring with k + 1 colors. Order the vertices and color them one by one. Since each vertex has at most k neighbors, one of the k + 1 colors has not been used on a neighbor, so there is always a good color for that vertex. In fact, we have shows that any graph in which every vertex has degree at most k can be colored with k + 1 colors. 1 (b) [ 10 ] In terms of n , what is the minimum number of edges a finite graph with chromatic number n could have? Prove your answer. n ( n − 1) Answer: 2 Solution: We prove this claim by induction - it holds for n = 1. Now assume the claim holds for n , and consider a graph of chromatic number n + 1. This graph must have at least one vertex of degree n , or else, by part a), it could be colored with only n colors. Now, if we remove this vertex, the remaining graph must have chromatic number n or n + 1 - if the chromatic number is n − 1 or less, we can add the vertex back and give it a new color, creating a good coloring with only n colors. By the inductive hypothesis, the n ( n − 1) n ( n − 1) n ( n +1) new graph has at least edges, so the original graph had at least + n = 2 2 2 edges. n ( n +1) The complete graph on n + 1 vertices has exactly edges, so the lower bound is 2 tight and the inductive step is complete.