Problem-Solving Using Graphs

Many problems being solved use graphs to aid in representation or in solution!

Traversing Graphs: Traveling Salesman

The Traveling Salesman problem is a classic example of an application of graph theory. The following video goes over a number of algorithms that can be used to attempt to solve this problem.

Graph Coloring: Map Coloring

The Four Color Theorem, mentioned before, is a theorem stating every planar graph can be properly colored in 4 colors.

As it turns out, 5 colors can be easily proven, as shown in the video below.

However, proving the 4 color theorem has been contentious. It was aided by computer, and some mathematicians worry about the validity of the proof because of this.

Think about it: What other problems have you seen that could or do use graphs?