Origins and Development of Graph Theory
Graph theory is a branch of mathematics dealing with the study of graphs that are defined as mathematical structures implemented to model pair-wise relations established between various objects belonging to a certain collection. The initial subject of the theory, which appeared as far back as in the 18th century, was the solution of recreational mathematical problems (Trudeau 7). However, with time, graph theory has developed into an extensive area of research currently applied in several scientific areas including chemistry, social disciplines, and IT.
Leonhard Paul Euler (1707-1783) was a Swiss mathematician whose activity marked the beginning of graph theory. He solved one of the toughest problems by creating the first graph to simulate time and place for a real situation and thereby laid the foundation of a new field of mathematics. His paper Seven Bridges of Köningsberg (published in 1736) is the first work on the topic, in which Euler used a formula that was further developed and generalized by Cauchy and L’Huillier and applied by Listing, who initiated a new branch of mathematics called topology (Trudeau 13).
The problem introduced in the paper was not a hypothetical one – it originated in the city of Königsberg (currently known as Kaliningrad). The city had seven bridges built to connect two islands with the mainland, and citizens often wondered if it was possible to walk over all of them only once. Having studied the map of the city and the layout of the bridges, Euler simplified and abstracted the problem to get rid of the redundant details; as a result, the city was represented as a picture consisting of connected dots. This made the solution quite easy: the only thing he had to do was to trace the graph with a pencil without lifting it, which proved that it was impossible to cross all the bridges only one time (Deo 32). However, Euler went further than just mere demonstration – he explained why traversing the edge once is impossible and provided characteristics that these graphs should possess to make the problem solvable. He introduced a concept of degree of nodes, which he defined as the number of edges touching a particular node. This helped Euler formulate his theory: traversing a graph exactly once became possible only under the condition that this graph had zero or two nodes having odd degrees. The graph that meets these requirements is now called the Eulerian circuit (path) (Trudeau 27).
The theory was further elaborated by Cayley, who took an interest in a particular type of graph – trees. His study of analytical forms arising from differential calculus made a great contribution to the development of theoretical chemistry. The results he obtained, along with those published by Pólya, laid the basis of the so-called enumerative graph theory that describes a class of combinatorial enumeration problems, which can be solved by counting graphs of certain types (both directed and undirected). Cayley managed to unite his discoveries on trees with ideas from mathematics; as a result of the fusion of the two disciplines, there appeared terminology that graph theory currently operates (Deo 35).
However, even though the theory had been introduced in 1736, the term ‘graph’ appeared not earlier than in 1878 in a paper published by Sylvester in Nature (the first textbook on graph theory was written much later, in 1936) (Deo 36).
One of the most complicated problems the theory had to deal with during its history was the four-color problem. The problem was first posed by Francis Guthrie in 1852 (though the first written record is a letter written by De Morgan to Hamilton). It runs as follows: “Is it true that any map drawn in the plane may have its regions colored with four colors, in such a way that any two regions having a common border have different colors?” (Harary 45). Different solutions were proposed by several prominent scholars (including Cayley, Kempe, and others); yet, none of them were correct. The problem marked the beginning of another stage of development of graph theory. Generalizations proposed by Tait, Heawood, Ramsey, and Hadwiger generated a new class of such-like factorization problems, which were later studied by Petersen and Kőnig. Thus, another branch, called extremal graph theory, was gradually getting momentum. Nevertheless, it should be noted that the solution to the problem had not been found until 1969 when it was done with the assistance of a computer (Trudeau 40).
The topology that originated from the theory continued its autonomous development in the second half of the 19th century. The works of such scholars as Jordan, Kuratowski, and Whitney enriched graph theory while with topological findings. Another flow of its data came from the application of the techniques of modern algebra, which was first illustrated in the works of Kirchhoff. In 1845, he published a paper in which Kirchhoff’s circuit laws were introduced. They allowed calculating the voltage and current in electric circuits (Trudeau 42).
Finally, the introduction of probabilistic methods (by Erdős and Rényi, who studied asymptotic probably of graph connectivity) was crucial for the appearance of one more branch of graph theory, which was called random graph theory and received a lot of attention of different scientists already in the 20th century (Deo 51).
Works Cited
Deo, Narsingh. Graph Theory with Applications to Engineering and Computer Science. Courier Dover Publications, 2016.
Harary, Frank. A Seminar on Graph Theory. Courier Dover Publications, 2015.
Trudeau, Richard J. Introduction to Graph Theory. Courier Corporation, 2013.