With the advent of computers, several problems turned out to be manifestation and application of graph theory. These are problems that are not very easy to solve for an individual with just a paper and pen. However, if the theory is known, application of this knowledge is very easy and thus the solutions are straightforward.
Discussed below are some famous problems that motivated a systematic study of graphs/networks.
Knight’s Tour: You have a knight that should move around the chess board visiting each square exactly once. Further, it should return to the same square. If you know what a hamiltonian circuit is, you can easily model the knight’s moves as a graph and solve this.
TimeTable: For m professors and n subjects, prepare an optimal timetable. Turns out to be a minimum coloring problem.
More such problems and their manifestation to graphs is discussed in this article.