CODEWITHSUNDEEP
binary-treediscrete-mathematics
ace84
ace84

Reputation: 13

What is the largest chromatic number of a binary tree?

This is a Discrete Math/Combinatorics Question from my homework, but I don't really understand the question.

Find largest chromatic number of a full binary tree given the following depths: (Check all that apply)

2, 3, 7, 12, 200

I understand that the chromatic number refers to the minimum color that you can color a graph or tree with the adjacent nodes or vertices being different colors.

So knowing this fact, I'm sure that the chromatic number for all full binary trees should be 2 since you can use two different color nodes to complete the tree. But they want me to find the largest chromatic number, which confuses me.

Am I missing something?

Upvotes: 0

Views: 3463

Answers (1)

templatetypedef
templatetypedef

Reputation: 373462

All trees are bipartite graphs and therefore 2-colorable. One way to see this is that a graph is bipartite iff it has no odd cycles, and since trees have no cycles at all, they must be bipartite. Therefore, two colors suffice regardless of the tree size.

Hope this helps!

Upvotes: 1

Related Questions