In this article, we will show that every tree is a bipartite graph.
Tree: A tree is a simple graph with N – 1 edges where N is the number of vertices such that there is exactly one path between any two vertices.
Bipartite: A graph is bipartite if we can divide the vertices into two disjoint sets V1, V2 such that no edge connects vertices from the same set. Every bipartite graph is 2 – chromatic.
Proof that every tree is bipartite
The proof is based on the fact that every bipartite graph is 2-chromatic.
Suppose a tree G(V, E). Let R be the root of the tree (any vertex can be taken as root). As we know there is only one path from R to any other vertex of the tree. Assign color red to vertices at an even distance from R and the color blue to vertices at an odd distance from R.
Vertices adjacent to each other cannot have the same color. If 2 vertices with the same color are adjacent then there exists more than one path from the root to these vertices.
For example, suppose two vertices v1 and v2 that are red and are adjacent. Both v1, v2 must be at an even distance from the root. But if we visit v2 through v1, it implies v2 is also at an odd distance from the root. This means there are two paths to reach v2, one of even length and the other of odd length. But there is exactly one path between any two vertices in a tree. Therefore, the same color vertices are not adjacent to each other.
We can also say that 2 paths from root to any vertex implies there is a cycle in the tree which is not possible.
We can bipartition the vertices by placing red vertices in one set and blue vertices in another set.
Hence, we can say that every tree is bipartite.
Read
Bipartite Graph is 2-Chromatic