HMMT 二月 2009 · TEAM2 赛 · 第 2 题

英文解析

2. [ 6 ] In a connected graph, it is possible to reach any vertex from any other vertex by followingthe edges. A tree is a connected graph with n vertices and n − 1 edges for some positiveinteger n . Suppose n ≥ 2. What is the chromatic number of a tree having n vertices? Proveyour answer.
   Solution: The chromatic number of any tree is 2. We show this by induction on the sizeof the tree. A tree with 2 nodes can clearly be 2-colored. Now, suppose a tree of size n − 1
   can be colored in 2 colors. Given a tree of size n , choose any leaf (node with only one edgecoming out of it), say l , of the tree, and color it red. The node it is adjacent to, say x , must be colored a different color, say blue. Using the inductive hypothesis, we can 2-color the treeformed by removing l , and we can choose the color of x to be blue and the other color to bered. Thus the entire tree on n vertices can be two-colored, completing the induction.