HMMT 二月 2009 · TEAM2 赛 · 第 2 题

HMMT February 2009 — TEAM2 Round — Problem 2

[ 6 ] In a connected graph, it is possible to reach any vertex from any other vertex by following the edges. A tree is a connected graph with n vertices and n − 1 edges for some positive integer n . Suppose n ≥ 2. What is the chromatic number of a tree having n vertices? Prove your answer.

解析

[ 6 ] In a connected graph, it is possible to reach any vertex from any other vertex by following the edges. A tree is a connected graph with n vertices and n − 1 edges for some positive integer n . Suppose n ≥ 2. What is the chromatic number of a tree having n vertices? Prove your answer. Solution: The chromatic number of any tree is 2. We show this by induction on the size of 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 edge coming 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 tree formed by removing l , and we can choose the color of x to be blue and the other color to be red. Thus the entire tree on n vertices can be two-colored, completing the induction.