• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q44E

Expert-verified Found in: Page 757 ### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # 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.

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.

See the step by step solution

## Step 1: 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.

## Step 2: 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). ### Want to see more solutions like these? 