For well over a century the most famous unsolved problem in graph theory and one of the most famous unsolved problems in mathematics was a map coloring problem called the Four Color Problem. This problem, dealing with determining whether a conjecture called the Four Color Conjecture was true or false, had a major impact on the development of graph theory. Indeed, in 1967 William T. Tutte wrote:
It would not be hard to present the history of graph theory as an
account of the struggle to prove the four color conjecture, or at least
to find out why the problem is difficult.