Proof that any tree is a bipartite graph

Published On :2021-09-10 15:11:00

 Theorem: Any tree is a bipartite graph

Proof: select a vertex as the root and color it white . 

Vertices in the first stage ( children of the root first level ) are colored black.

Vertices in the second stage ( second level ) are colored white.

We continue this process and color vertices in successive levels with different colors

( white & black ).

Since our graph is a tree, then vertices in the same level are not adjacent

( If any vertices of the same level are adjacent we get a cycle ).

Thus a tree is a bipartite graph .

Ex: