# Is every acyclic graph 2-colorable?

Every acyclic graph can be transformed structurally to a tree. Therefore, every node on odd numbered levels can be colored with color $X$ and every node on even numbered levels can be colored with color $Y$. Is the reasoning valid?

• Yes, the reasoning is valid. As a clarification, every acyclic graph is a tree, no conversion is needed. – Gabriel Tigerström Mar 2 '17 at 12:02
• An acyclic graph is a tree iff it is connected. More generally, it is a forest. – Yuval Filmus Mar 2 '17 at 13:27
• Valid but not really needed. If your graph has by hypothesis no cycles, it is trivially bipartite. – quicksort Mar 2 '17 at 14:02
• "Every acyclic graph can be transformed structurally to a tree." No, every acyclic graph is a tree or a union of trees. That's the definition of tree. – David Richerby Mar 2 '17 at 21:58

## 1 Answer

An acyclic graph, usually known as a forest, is a collection of disjoint trees. It is only a tree if it is connected. Since trees are 2-colorable (for the same reason you mention), it follows that forests are also 2-colorable.

It is also possible to reduce the general case to the connected case: given a forest, you can join the different connected components to form a tree. The resulting tree is 2-colorable, and the same 2-coloring is also valid for the original forest.