1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.