$(5$ pts$.)$ Determining if a graph is bipar$$te$.$ A graph G $=($V$,$ E$)$ is bipar$$te if its ver$$ces

can be par$$oned into two sets V$1$ and V$2($i$.$e$.,$ V $=$ V$1\backslash$cup V$2$ and V$1\backslash$cap V$2=)$ so that

every edge has one endpoint in V$1$ and another endpoint in V$2.$ Equivalently, G is bipar$$te

if its ver$$ces can be colored red or blue so that every edge has one red endpoint and one

blue endpoint. $($V$1$ consists of the red ver$$ces while V$2$ the blue ver$$ces$.)$ Many real$-$world

problems are modeled by bipar$$te graphs $$ for example, when matching employees to jobs,

V$1$ can represent the set of all employees, V$2$ the set of all jobs and there is an edge from an

employee to a job if the employee is qualified for the job.

a$.(1$ pt$.)$ Explain why an odd cycle $($i$.$e$.$ a cycle of odd length$)$ is not bipar$$te$,$ and

why a graph that has an odd cycle as a subgraph is not bipar$$te$.$

Here$$s a standard way of determining if a given connected graph G is bipar$$te: Star$$ng at

some arbitrary node s$,$ run BFS$($G$,$ s$).$ Addi$$onally record each node v$$s layer in the tree

as v$.$layer. $($That is$,$ if v in Li then v$.$layer $=$ i$.)$ When BFS$($G$,$ s$)$ ends, go through every

edge. If some edge e $=$ uv is a cross edge and u$.$layer $=$ v$.$layer, return $$G is not a

bipar$$te graph.$$ Otherwise, if every cross edge does not sa$$sfy this condi$$on$,$ return $$G is

a bipar$$te graph.$$

b$.(2$ pts$.)$ Explain why the above algorithm is correct. That is$,$ argue that when the

algorithm returns $$G is not a bipar$$te graph$$ then G is indeed not a bipar$$te graph.

On the other hand, when the algorithm returns $$G is a bipar$$te graph$$ then explain

why G is indeed a bipar$$te graph. That is$,$ which ver$$ces should go to V$1$ and which

ver$$ces to V$2?$

c$.(2$ pts$.)$ It is not difficult to check that the above algorithm runs in linear $$me $($i$.$e$.$

O$($n $+$ m$)$me$).$ This $$me around, describe a linear $$me algorithm that checks if a

connected graph is bipar$$te or not based on DFS$.$ Please explain why your algorithm

is correct and why it runs in linear $$me