**Graph Theory**

Roxana Popescu, Dongchen Li, and Celia Karpatkin

The Seven Bridges of Konisburg

Four-Color Map Theorem

It states that no more than four colors are needed to color a map so that adjacent regions of the map do not have the same color.

In order for a map to meet the requirements for the four color theorem:

The regions on the map must be contiguous

The regions on the map must have a finite area and a finite perimeter

The corners where regions meet are not considered adjacent

Using graph theory, each region can be represented by a vertex and each boundary between regions can be represented by an edge.

The Traveling Salesman

If we have a list of cities and the distances between them, what is the shortest path to visit every city once and then return to the first city?

**A graph in discrete mathematics is a way of interpreting data as a set of vertices and edges. It is at the origin of the branch of mathematics known as Topology.**

Applications

Solving the TSP

Genome Sequencing

NASA Starlight

Art

this image uses 27,846 carefully placed cities to create the Mona Lisa.

The World Tour

this shows a world tour of length 7,516,353,779m through all 1,904,711 cities in the world. It is at most 0.076% off the ideal route.

**Sources**

**http://www.utm.edu/departments/math/graph/**

http://jgaa.info/

http://www.ics.uci.edu/~eppstein/pubs/graph.html

http://www.mathpages.com/home/kmath266/kmath266.htm

http://www.huffingtonpost.com/david-h-bailey/kenneth-appel-four-color-theorem_b_3233775.html

http://jgaa.info/

http://www.ics.uci.edu/~eppstein/pubs/graph.html

http://www.mathpages.com/home/kmath266/kmath266.htm

http://www.huffingtonpost.com/david-h-bailey/kenneth-appel-four-color-theorem_b_3233775.html

As often happens in mathematics, a simple problem began the creation of a new field of mathematics: In the 1700's the townspeople of old Königsberg, East Prussia, wondered if was possible to take a walk around their town in such a way as to cross each of the seven bridges exactly once.

History

The great mathematician Euler began by pointing out that the shapes and sizes of the land masses and bridges did not matter--so he reduced (in words) the drawing above to the following graph.This simple idea began the study of graph theory!

"Is there a path which traverses every edge in this graph exactly once?"

SO here is the new question

Euler's answer is "No. It is impossible."

And here is why...

Theorem

A connected graph has an Euler path (which is not a circuit) if and only if it has exactly two vertices with odd degree.

Proof

The four color map theorem was first conjectured in 1852 by Francis Guthrie.

Several failed attempts were made to prove the theorem until 1976 when it was proven by Kenneth Appel and Wolfgang Haken by using a computer.

However, this proof was met with criticism

In 2005, Werner and Gonthier used a theorem proving software used by mathematicians to finally prove the theorem.

The 1976 proof began with the assumption that if the four color theorem is false then there must be a map with the smallest number of regions that requires four colors.

Using the computer, 1,936 configurations of possible counterexamples were found.

The computer then checked all of these configurations and determined that all of these could be colored by using only four colors.

By proving that there was no counterexample, the theorem was proven to be true.

Origins are unclear, but first formulated as a mathematical problem in the 1800s by W. R. Hamilton and Thomas Kirkman.

became popular in the 1950s and 60s as it was applied to chemistry, physics, and computer science

in the 1990s, four mathematicians created the computer program Concorde to solve TSP problems within 2-3% accuracy

Concorde was used to solve a 85,900-city problem, a microchip layout problem, exactly

We can simply find the brute-force solution by trying every possible route and finding the shortest path. but this gets tedious.

various dynamic programming algorithms exist for solving or approximating the solutions.

the branch-and bound algorithm consists of finding upper and lower bounds for the solution.

the upper bound is the "Nearest Neighbor" algorithm

the lower bound is more complicated to find--find a min spanning tree, add vertice back in