This question has puzzled mathaticians for a very long time. Hopefully you didn't spend too much time looking for a graph with a chromatic number of 5 since it has now been proved that any graph will have a chromatic number of at most 4. This is called the Four Color Problem.
Map makers have known for a very long time that it only takes four colors to color a map so that none of the borders have the same color. In 1852, Francis Guthrie became intrigued by this and wanted to prove it. He passed the problem along to his brother, who then asked his profesor, DeMorgan. Over time, there were many conjectures and proofs offered to show that this was true. Even mathematicians make errors though and many flaws were found. In 1976 Appel and Heken developed a proof that has so far stood the test of time. The proof uses a computer and takes up a whole book. Heken has taken bets on the validity of their proof, so far he has won.