# 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