The Development
Although Euler's first paper about the Königsberg Bridges did not include a modern approach, his later papers did. His later paper included a more modern graph.
That graph looks like:
Euler was able to come to this conclusion in 1736 (Prakash, 2018)
. This development led to what mathematicians now refer to as Eulerian graphs.
More than 100 year later Francis Guthrie noticed that each country in England could be colored with only 4 colors, such that no adjacent countries had the same color. He then
conjectured that the four-color problem was true. Francis shared this information this his mentor, Augustus De Morgan. Morgan then published about this problem and shared it with
Sir William Rowan Hamilton.
A few years later Sir William Rowan Hamilton, an Irish mathematician, came up with the problem of "A Voyage around the World". This was a wooden game with 20 holes carved
into its surface, these holes represented cities, or in the context of graph theory, vertices. The goal was to travel along the edges to visit each other city exactly once and end
up where you started, at the first city. This lead to the development of Hamiltonian Cycles/Circuits. Below is a picture of what this game would look like.
A few years after the development of Hamiltonian Cycles, Alfred Kempe wrote a proof about the four-color problem. This proof was accepted for about a year, before Percy Heawood found
a mistake in the proof. For a very long time, mathematicians worked to find a proof of this theorem. Until 1976, no such proof existed. In 1976 a computer-assisted proof was finally made
by Kenneth Appel and Wolfgang Haken. But because of the use of the computer, many mathematicians did not accept this proof; they did not and most still do not consider it valid. In 1996,
an algorithm was made based on this proof. It simplified the process but a computer was used to simplify that would have been impractical to do by hand. In 2001,an alternative proof was
made, that used less computer programming, but still used a little bit, and finally in 2005 a formalized proof was made. This proof used minimal computer programming to verify very
specific cases.
Even thought graph theory is made easier by the use of computers, many mathematicians still do not consider a computer-assisted proof as a true proof.
One mathematician of note is Paul Erdös. He worked on many different areas of mathematics, but here we are only concerned with his work with graph theory. His biggest contribution
was coming up with the De Bruijn-Erdös Theorem, a proof for coloring infinite graphs from its finite subgraphs. It basically says that It states that, when all finite subgraphs can
be colored with c colors, the same is true for the whole graph. He often offered small prizes for solutions to various unresolved problems, some of which are still active even
after his death in 1996 (Mastin,2010)
.
