# Proving that Breadth-First Search (BFS) results in a bipartition of a tree

In my studies of discrete mathematics, I've learned that a tree graph is inherently bipartite. I'm interested in finding an algorithmic approach to determine its bipartition. It seems to me that Breadth-First Search (BFS) could be a reasonable method for this task.

However, I'm struggling with the formal proof of this concept. Could anyone provide a detailed explanation or proof showing that applying BFS to a tree will indeed result in a valid bipartition? Any insights or resources would be greatly appreciated.

Let $$r$$ be an arbitrary root.
Denote by $$d(v)$$ the distance from $$r$$ to $$v$$. As you might know, every edge goes either between vertices of the same layer, ie, vertices of same $$d(v)$$, or between vertices in consecutive layers.
Now, there cannot be an edge going from one vertex in layer $$\ell$$ to another vertex in layer $$\ell$$ because then we would have a cycle of length $$2\ell+1$$, hence every edge goes between consecutive layers.
Let $$L$$ be the set of vertices with even $$d(v)$$ and $$R$$ the ones with odd $$d(v)$$.
It follows that there are no edges inside neither $$L$$ nor $$R$$.