Algorithm

Question

A graph (V, E) is bipartite if the vertices V can be partitioned into two subsets
L and R, such that every edge has one vertex in L and the other in R.
(a) Prove that every tree is a bipartite graph.
(b) Prove that a graph G is bipartite if and only if every cycle in G has an even
number of edges.

Answer 1

(a)
let V1 contain all vertices at even number levels (i.e. level 0,level 2, etc.) of the tree.
let V2 contains all vertices at odd number levels (i.e. level 1,level 3, etc.) of the tree.
there can not be edges from a vertex in V1 to a vertex in V1, since in a tree a vertex at level m can only be connected to a vertex at level m-1 or level m+1
similarly, there can not be edges from a vertex in V2 to a vertex in V2, since in a tree a vertex at level m can only be connected to a vertex at level m-1 or level m+1
therefore every edge has one vertex in V1 and the other in V2 thus the tree is a bipartite graph