Report

Coloring Warm-Up A graph is 2-colorable iff it has no odd length cycles 1: If G has an odd-length cycle then G is not 2colorable Proof: Let v0, …, v2n+1 be an odd length cycle (n≥1). Suppose G can be colored with two colors red and blue. Without loss of generality [WLOG] color v0 red. Then v1 must be colored blue since v0 and v1 are adjacent. Then v2 must be colored red, and in general, all even-indexed vertices must be colored red and all odd-indexed vertices must be colored blue. But v0=v2n+1 must get both colors, contradiction. A graph is 2-colorable iff it has no odd length cycles 2: If G has no odd-length cycles then G is 2colorable. How to define the coloring? Helpful Def. The distance of one vertex from another is the length of the shortest path between them. Proof: Pick any connected component. Pick an arbitrary vertex v. Color all vertices at even distance from v with one color and all vertices at odd distance from v with the other color. • It suffices to prove that for every n, there are no nodes in G that (a) are distance n apart but (b) also have a path between them of length m, where one of m, n is even and the other is odd. • Suppose there were. By WOP there is a least such n, and such a pair of nodes v, w. • Then the two paths have no vertices in common except the beginning and end. • But the round trip out on one path and returning on the other path is a cycle of length m+n, which is odd, contradiction. QED