Question

Every tree with two or more vertices is 2-chromatic

Answer 1

Answer:

Step-by-step explanation:

Answer 2

To prove:

Every tree with two or more (n ≥ 2) vertices is 2-chromatic.

where n = total number of vertices.

Proof:

Let M be a tree with two or more vertices.

We need to consider any vertex n of M and let us assume M is rooted at vertex n.

First, we need to assign a color code of 1 to n.

Let us assign a color code of 2 to all vertices adjacent to n.

Let n1, n2,..., x. be the vertices assigned with color 2.

Those which are adjacent to n1, n2,..., x are assigned with color 1.

We need to continue this process till every vertex in M has been assigned the color.

We observe that in M, vertices with odd distances from n will have a color code of 2, and those which are at even distances from n will have a color code of 1.

Therefore while going through any path in M, the vertices will have and show alternating colors.

Due to the presence of only one root and one path between two vertices within a tree, none of the two adjacent vertices will have the same color code.

Thus M will be colored in two colors.

Hence M is di-chromatic.

#SPJ3