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

### Select your language

Suggested languages for you:

Americas

Europe

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

### Answers without the blur.

Just sign up for free and you're in.

# 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?

Sign up for free to discover our expert answers

## Recommended explanations on Math Textbooks

94% of StudySmarter users get better grades.