Graph Theory and Its Applications With A Focus on Assignment Problems

Temidayo Adekunle, Malcolm Boachie

graph theory, networks of points

Graph theory is a branch of mathematics that deals with networks of points that are connected by lines. The beginnings of graph theory stemmed from recreational math problems and number and strategy games such as chess, but as a mathematical area of study, graph theory can be traced to famous mathematician Leonhard Euler. There was an old puzzle that concerned finding a path across every one of seven bridges that span a forked river around an island, but the path could only be created by crossing each bridge once. This is the famous Konigsberg bridge problem. Euler stated that no such path existed, and he was correct, although he could only prove it using the physical arrangement of the bridges and not in any mathematical terminology. His discovery of no such path paved the way for the first theorem of graph theory.

           A more specific focus in graph theory that we will be focusing on is graph coloring. A graph is properly colored when adjacent vertices of a graph connected by an edge are different colors. An easy way to ensure that adjacent vertices are colored differently is to give every vertex a unique color. However, this is a cumbersome method when it comes to coloring a large graph, and it is generally an inefficient method. This leads to the grand Four Color Theorem. The formal way of stating this theorem is that the chromatic number of a planar graph is no greater than four. A chromatic number is the least number of colors needed for the coloring of a graph. A planar graph is a dot-and-line diagram on a plane without any edges crossing except for at the established vertices. In other words, the Four Color Theorem just states that a planar graph can be colored using at most four colors. This is useful for things such as coloring a world map, because it would only take 4 colors to label every country. This theorem was originally conjectured in the 1850s by South African mathematician Francis Guthrie. In 1879 it was incorrectly proved by amateur mathematician Alfred Kempe but his proof held as valid until 1890 when British mathematician Percy Heawood found an error in Kempe’s proof and ended up proving the five color theorem. The Four Color Theorem was official proved by American mathematicians Kenneth Appel and Wolfgang Haken in 1976 using a case by case analysis carried out by computer. This was the first major theorem to be proved using a computer, which is why it caused controversy in the math world since computers are not without flaws. Nevertheless, the proof is still upheld and there have been simpler proofs that shrank the number of configurations the computer has to go through, but no proof without the use of computers has been found yet.