Let ??=(??,??) be a graph for which each vertex is colored either black or white (but not both). We say that vertex ???? is integrated if at least half of its neighbors (those connected by one edge to ??) have a different color than ??. Furthermore, we say that a coloring of a graph is integrated if every vertex in the graph is integrated.

(a) Show that every graph in which every cycle is of even length has an integrated coloring. Consider the following algorithm: pick an uncolored vertex, color it white, color each of its neighbors black and repeat. Why will this procedure terminate in an integrated coloring? (b) Prove that every graph has an integrated coloring. Consider the following algorithm: First, color every vertex white. Next, if there is a vertex that is not integrated, flip its color. When this algorithm terminates, it will yield an integrated coloring. Prove that the process always terminates. (Hint: focus on the number of mixed edges those whose end-points are of different colors.) What logical principle did you use to prove termination?