Question

Show that every forest can be colored using two colors.

Short answer

Therefore, every forest can be colored using two colors.

Step-by-step solution

General form

Definition of Forest: an undirected graph with no simple circuits.

Definition of tree: A tree isa connected undirected graph with no simple circuits.

Definition of Circuit:It is a path that begins and ends in the same vertex.

Bipartite graph(Definition): It is a simple graph whose vertices can be partitioned into two sets \({{\bf{V}}_{\bf{1}}}\) and \({{\bf{V}}_2}\) such that there are no edges among the vertices of \({{\bf{V}}_{\bf{1}}}\) and no edges among the vertices of \({{\bf{V}}_2}\), while there can be edges between a vertex of \({{\bf{V}}_{\bf{1}}}\) and a vertex of \({{\bf{V}}_2}\).

Proof of the given statement

Given that, T is a tree.

To prove: T can be colored with two colors.

Let \({{\bf{V}}_{\bf{1}}}\) contains all vertices at level 0, level 2, level 4, etc., of the tree T and let \({{\bf{V}}_{\bf{1}}}\) contains all vertices at level 1, level 3, level 5, etc.,

There cannot be edges from a vertex in \({{\bf{V}}_{\bf{1}}}\) to a vertex in \({{\bf{V}}_{\bf{1}}}\), as a vertex at level h can only be connected to a vertex at level h-1 or level h+1.

Similarly, there cannot be edges from a vertex in\({{\bf{V}}_2}\)to a vertex in\({{\bf{V}}_2}\), as a vertex at level h can only be connected to a vertex at level h-1 or level h+1.

It is possible that there are edges from a vertex in \({{\bf{V}}_{\bf{1}}}\) to a vertex in \({{\bf{V}}_2}\) and thus the graph is bipartite.

Since a bipartite graph can be colored using two colors, T can be colored with two colors.

So, we can color each connected component separately. For each of these connected components, first root the tree, the color all vertices at even levels red and all vertices at add levels blue.

Conclusion: So, a tree can be colored with two colors.

Hence proved.