Name ___________________________________________________

1. Prove that the 5-coloring problem -- given a graph, check whether it can be colored in 5 colors -- is NP-hard.