HMMT 二月 2009 · TEAM1 赛 · 第 3 题

英文解析

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 chromaticnumber of G is at most k + 1.
   Solution: We find a good coloring with k + 1 colors. Order the vertices and colorthem one by one. Since each vertex has at most k neighbors, one of the k + 1 colors hasnot been used on a neighbor, so there is always a good color for that vertex. In fact, wehave shows that any graph in which every vertex has degree at most k can be coloredwith k + 1 colors.
   (b) [ 10 ] In terms of n , what is the minimum number of edges a finite graph with chromatic 1
   number n could have? Prove your answer.
   n ( n − 1)
   Answer:
   Solution: We prove this claim by induction - it holds for n = 1. Now assume the 2
   claim holds for n , and consider a graph of chromatic number n + 1. This graph musthave at least one vertex of degree n , or else, by part a), it could be colored with only ncolors.
   Now, if we remove this vertex, the remaining graph must have chromatic number n orn + 1 - if the chromatic number is n − 1 or less, we can add the vertex back and give it anew color, creating a good coloring with only n colors. By the inductive hypothesis, then ( 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 istight and the inductive step is complete.2