StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q44E

Expert-verifiedFound in: Page 757

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.

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.**

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).

94% of StudySmarter users get better grades.

Sign up for free