Answer Happy

The goal of this problem is to show that a graph is 2-colorable if and only if it contains no closed walks of odd length. a) Prove that if a graph contains a closed walk of odd length then it is not 2-colorable. b) Prove that every tree is 2-colorable. c) Prove that every forest is 2-colorable. d) Suppose that G contains contains no closed walks of odd length. Let H be a maximal spanning forest of G and let f be a 2-coloring of H. Prove that f is a 2-coloring of G, by showing that every edge of G that isn't in H must connect two differently-colored vertices.