Origins and Development of Graph Theory prior to 20th Century
Brief Overview of Graph Theory which revolutionised the way many complicated problems were looked at and were solved.
What is Graph Theory?
Graph Theory is a branch of Mathematics in which we study graphs.
Graphs are mathematical structures which consists of a set V of vertices and set E of edges. It is used to model pair-wise relations between objects from a certain collection. Vertices(also called nodes) are represented as points in the plane and edges are represented as the line segments connecting them(see figure).
Origins of Graph Theory
In a 1670 letter to Christian Huygens (1629–1695), the celebrated philosopher and mathematician Gottfried W. Leibniz (1646–1716) wrote as follows:
I am not content with algebra, in that it yields neither the shortest proofs nor the most beautiful constructions of geometry. Consequently, in view of this, I consider that we need yet another kind of analysis, geometric or linear, which deals directly with position, as algebra deals with magnitude.
Known today as the field of Topology, Leibniz’s Geometry of Position was slow to develop as a mathematical field. As C. F. Gauss (1777–1855) noted in 1833,
Of the geometry of position, which Leibniz initiated and to which only two geometers, Euler and Vandermonde, have given a feeble glance, we know and possess, after a century and a half, very little more than nothing.
The ‘feeble glance’ which Leonhard Euler (1707–1783) directed towards the geometry of position consists of a single paper now considered to be the starting point of modern graph theory. The paper published by Euler appeared in Commentarii Academiae Scientiarum Imperialis Petropolitanae in 1736 on the Seven Bridges of Königsberg is regarded as the first paper in the history of graph theory. He created first graph to simulate a real time place and situation to solve a problem which was then considered one of the toughest problems. Yet from such deceptively simple origins, graph theory has grown into a powerful and deep mathematical theory with applications in the physical, biological, and social sciences.
Brief Overview of Seven Bridges of Königsberg Problem
The Königsberg bridge problem originated in the city of Königsberg, formerly in Prussia but, now known as Kaliningrad and part of Russia, located on the river Pregel. The city had seven bridges, which connected two islands with the main-land via seven bridges. People staying there always wondered whether was there any way to walk over all the bridges once and only once and return to the same place were they started the walk.
In, 1736 Euler came out with the solution in terms of graph theory. He proved that it was not possible to walk through the seven bridges exactly one time. In coming to this conclusion, Euler formulated the problem in terms of graph theory. Each landmark was represented as a point(node) and every bridge as an edge. This led to the formation of graph theory!
Hamilton’s “A Voyage Round the World” Puzzle
In 1857, Irish mathematician Sir William Rowan Hamilton, invented a puzzle A Voyage round the world. It consisted of a wooden dodecahedron, with a peg at each vertex of the dodecahedron, and string. The twenty vertices of the dodecahedron were labelled with different cities in the world. The object of the puzzle was to start at a city and travel along the edges of the dodecahedron, visiting each of the other 19 cities exactly once, and end up at the first city. This puzzle led to the development of what we now call Hamilton Circuits/Cycles.
Four Color Theorem
In October 23,1852, an ex-student of Augustus De Morgan, Francis Guthrie, noticed that the counties in England could be colored using four colors so that no adjacent countries were assigned the same color. On this evidence, he conjectured that the four color theorem was true. Francis told his brother Frederick, at that time a student of De Morgan, about this problem. Frederick in turn asked his teacher De Morgan about his brother’s conjecture. De Morgan was extremely interested in this problem and publicised it throughout the mathematical community. In fact, the first written reference to the conjecture can be found in a letter from De Morgan to Sir William Rowan Hamilton. Although De Morgan thought Hamilton would be interested in this problem, Hamilton apparently was not interested in it, because it had nothing to do with quaternions.
Perhaps the most notorious fallacious proof in all of mathematics is the incorrect proof of the four color theorem published in 1879 by a London mathematician, Alfred Kempe. Mathematicians accepted his proof as correct until 1890, when Percy Heawood found an error that made Kempe’s argument incomplete.
In 1976, after a long history of failed attempts to prove this, Kenneth Appel (1932 — ) and Wolfgang Haken (1928 — ) published a computer-assisted proof which many mathematicians were unwilling to accept as valid.
Even after two centuries of its existence, Graph Theory remains an active field of research in the Mathematical and Computer Science Community.
