Prove that all trees are bipartite

I've been trying to prove this for a while. I can think about it intuitively, but I can't come up with a formal proof. I would appreciate some help.

Here's how I'm thinking about it

Let T be the given tree. Let V(T) be the set of vertices of T. We can create an isomorphism of T, call it f, that takes any vertex v in V(T) and makes it a root node. f takes all vertices that v is connected to and puts them on the second row of vertices of the isomorphism. f then takes all vertices connected to the vertices of the second row and adds them to a third row. This process continues until all vertices have been added to this isomorphic tree, call it T'. We can partition the vertices of T' into two groups, A and B. A will contain all vertices from even numbered rows of T', and B will contain all vertices from odd numbered rows from T'. Thus, we've created a bipartition of T', so T is a bipartite graph.

I hope I'm making my ideas clear. I'm essentially taking the tree T and converting it to a form

  *

 / \

*   *

etc...

and taking the alternating rows and putting them into two groups. These become the bipartition.

I'm trying to express my idea more formally. Would anyone be kind enough to help me out here.

Thank You.

The basic idea is fine.

Pick a node $v$ of $T$ to be the root. Let $u$ be any node of $T$; since $T$ is a tree, there is a unique path $P_u$ from $v$ to $u$. (Why?) Let $f(u)$ be the length of $P_u$. Let $V_E$ be the set of nodes for which $f(u)$ is even, and let $V_O$ be the set of those for which $f(u)$ is odd. Finish by showing that every edge of $T$ has one endpoint in $V_E$ and the other in $V_O$.

You've pretty much got it. Perhaps an easier way to say what you've said is take a vertex $v_0$ and put it in set $A$. Take any vertex in the tree that is an even number of edges away and put it in $A$. Put the rest in $B$.

If two vertices $v_1, v_2$ in $A$ are connected by edge $e$ then we can make a loop with the path from $v_0$ to $v_1$, $v_0$ to $v_2$, and edge $e$. Then the original set we were pulling the vertices from is not a tree. Thus, doing the prior process for a tree results in no $2$ vertices in $A$ being connected. Similarly, this holds for $B$. Then we have shown that a tree is bipartite.

Your reasoning seems to be OK. Start from the root and write next to each vertex a number of how many edges you need to pass in order to reach it. At the end put the odd-numbered vertices in one set and the even-numbered in the other. Obviously two vertices from the same set aren't connected, as in a tree there's only one path from one vertex to another (Note that all neigbours from one vertex are of different parity, compared to it).

Actually it's well known that a graph is bipartite iff it contains no cycles of odd length. A tree contains no cycles at all, hence it's bipartite.