GRAPH THEORY PLEASE ANSWER USING INDUCTION Use proof by ind

GRAPH THEORY - PLEASE ANSWER USING INDUCTION

Use proof by induction to prove that if T is a tree, then (the chromatic number)(T) 2. Hint: Use induction on the number of vertices.

Solution

We know that for a tree with one vertex, the chromatic number aka the minimum number of available colorings would be 1. Now, if the number of vertices are 2 or more, then chromatic number is always 2. Let us see how.

Base Case:

For a tree with number of vertices 2, we need two colors to cover all the vertices such that no two adjecent vertices have same color. Therefore, the chromatic number is 2.

For a tree with number of vertices 3, we must have two vertices connected to a common vertex by two edges. Therefore, the middle vertex will have one type of color and the end vertices will have a second type of color. Therefore we can color the tree using two colors. Therefore, the chromatic number is 2.

Asumption:

Now let us say that a tree with k vertices requires only two colors.

Hypothesis:

On adding 1 more (edge+vertex set) to the previous graph (the one in our asumption), we will get a tree where we can use the color for this additional vertex different than the color of the vertex it is directly attached to. Therefore, we can color this graph using two colors as well. Hence, the chromatic number of this graph is 2 as well.

Therefore, chromatic number of a tree can be either 1 or 2.