Question

Show that every tree can be colored using two colors. The rooted Fibonacci trees \({\bf{Tn}}\) are defined recursively in the following way. \({\bf{T1}}\)and\({\bf{T}}2\) are both the rooted tree consisting of a single vertex, and for \({\bf{n = 3, 4,}}...{\bf{,}}\) the rooted tree \({\bf{Tn}}\) is constructed from a root with \({\bf{Tn - }}1\) as its left subtree and \({\bf{Tn - 2}}\) as its right subtree.

Short answer

Color the root of the tree Blue. Next, color all vertices at level 1 Red, all vertices at level 2 Blue, all vertices at level 3 red, and so on.

Step-by-step solution

Definition

A tree is an undirected graph that is connected and that does not contain any simple circuits.

The level of a vertex is the length of the path from the root to the vertex.

Assuming color to the trees

To prove: Every tree can be colored using two colors.

Let us use the two colors Red and Blue. Color the root of the tree Blue. Next, color all vertices at level 1 Red, all vertices at level 2 Blue, all vertices at level 3 Red, and so on.

Since a vertex v at level h can only be directly connected to a vertex at level h-1 or at level h+1, the vertex v always has a different color than the vertices it is connected to (as they are in the previous and the following level).