4. Graded Problem (Page limit: 1 sheet; 2 sides) A (valid) graph coloring is to assign colors to vertices of a graph such that for every edge {u, v} the two vertices are assigned different colors Prove that a graph is bipartite iff it can be colored with two colors. . Find an algorithm, that upon an input graph, either produces a (valid) graph coloring with two colors, or outputs "No" when it cannot be colored with two colors. At most how many colors are needed to color in an undirected graph with exactly one cycle of odd length? . Find an efficient algorithm, that uses two colors to color all but one vertex for an undirected graph with exactly one cycle of odd length