Given an undirected graph G = (V, E), a k-coloring of G is a function c . V → {0, 1, . . . , k – 1} such that c(u) ≠ c(ν) for every edge (u, ν) ∈ E. In other words, the numbers 0, 1, . . . , k − 1 represent the k colors, and adjacent vertices must have different colors.

a. Show that any tree is 2-colorable.

b. Show that the following are equivalent.

1. G is bipartite.

2. G is 2-colorable.

3. G has no cycles of odd length.

c. Let d be the maximum degree of any vertex in a graph G. Prove that we can color G with d + 1 colors.

d. Show that if G has O(|V|) edges, then we can color G with O(√|V|) colors.