Given the linked$-$list representation of an undirected graph G $=($V$,$ E$)$

with n $=|$V $|$ and m $=|$E$|,$ please design an O$($n $+$ m$)-$time algorithm to decides if

G contains an odd cycle in G$.$ Please provide the Pseudo$-$code of your algorithm,

and briefly argue the correctness of your algorithm and argue the running time of

your algorithm. $($Hints: modify the BFS$,$ DFS$,$ or the algorithm for the Testing

Bipartiteness problem.$)$

I need the correctness with proof like inductive proof $or$ loop invarience etc.