Let $G = (V, E)$ be a forest, prove that there always exists a function $f:V\to \{0, 1\}$ such that $(u, v)\in E$ so $f(u)\neq f(v)$

Question

I have been looking everywhere for answers but I do not understand how can there be a function that takes a vector from a graph and returns a $0$ or $1$ and some how it won't repeat itself.

Can you please help me?

I understand the concept of a forest and believe I could start with a contradiction of taking two vectors that are different and getting the same answer.

Please let me know what I can do with that or if there is other way to prove it.

Answer 1

Forest is a bipartite graph since it has no odd lenght cycles (it has no cycles at all). So color vertices in one partition with number $0$ and all other with $1$ and you are done.