$3$ Bipartite Graph $(25$ pts$)$

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$)(10$ pts$)$ Prove that every tree $($not necessarily binary$)$ is a bipartite graph. Hint: demonstrate how

to partition the vertices of an arbitrary tree into the two sets and prove that this partitioning satisfies

the definition$/$conditions of a bipartite graph.

$($b$)(15$ pts$)$ Design an efficient algorithm that determines whether a given undirected connected graph

is bipartite. Write down the pseudocode, analyze its running time and prove that your algorithm is

correct. No points will be given without the proof.