Editing Graph theory (section)

== History ==
[[File:Konigsberg bridges.png|thumb|The Königsberg Bridge problem]]
The paper written by [[Leonhard Euler]] on the [[Seven Bridges of Königsberg]] and published in 1736 is regarded as the first paper in the history of graph theory.<ref name="Biggs">{{Citation|author1=Biggs, N. |author2=Lloyd, E. |author3=Wilson, R. |title=Graph Theory, 1736-1936|title-link=Graph Theory, 1736–1936|publisher=Oxford University Press|year=1986}}</ref> This paper, as well as the one written by [[Alexandre-Théophile Vandermonde|Vandermonde]] on the ''[[Knight's tour|knight problem]],'' carried on with the ''analysis situs'' initiated by [[Gottfried Wilhelm Leibniz|Leibniz]]. Euler's formula relating the number of edges, vertices, and faces of a convex polyhedron was studied and generalized by [[Augustin-Louis Cauchy|Cauchy]]<ref name="Cauchy">{{Citation|author=Cauchy, A. L.|year=1813|title=Recherche sur les polyèdres - premier mémoire|journal=[[Journal de l'École Polytechnique]]|volume= 9 (Cahier 16)|pages=66–86|postscript=.}}</ref> and [[Simon Antoine Jean L'Huilier|L'Huilier]],<ref name="Lhuillier">{{Citation|author=L'Huillier, S.-A.-J.|title=Mémoire sur la polyèdrométrie|journal=Annales de Mathématiques|volume=3|year=1812–1813|pages=169–189|postscript=.}}</ref> and represents the beginning of the branch of mathematics known as [[topology]].

More than one century after Euler's paper on the bridges of [[Königsberg]] and while [[Johann Benedict Listing|Listing]] was introducing the concept of topology, [[Arthur Cayley|Cayley]] was led by an interest in particular analytical forms arising from [[differential calculus]] to study a particular class of graphs, the ''[[tree (graph theory)|tree]]s''.<ref>{{citation|first=A.|last=Cayley|author-link=Arthur Cayley|year=1857|title=On the theory of the analytical forms called trees|journal=[[Philosophical Magazine]]|series=Series IV|volume=13|issue=85|pages=172–176|doi=10.1017/CBO9780511703690.046|isbn=9780511703690|url=https://rcin.org.pl/dlibra/docmetadata?showContent=true&id=173708|url-access=subscription}}</ref> This study had many implications for theoretical [[chemistry]]. The techniques he used mainly concern the [[enumeration of graphs]] with particular properties. Enumerative graph theory then arose from the results of Cayley and the fundamental results published by [[George Pólya|Pólya]] between 1935 and 1937. These were generalized by [[Nicolaas Govert de Bruijn|De Bruijn]] in 1959. Cayley linked his results on trees with contemporary studies of chemical composition.<ref name="Cayley1">{{Citation|author=Cayley, A.|year=1875|journal=Berichte der Deutschen Chemischen Gesellschaft|title=Ueber die Analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen|volume=8|pages=1056–1059|doi=10.1002/cber.18750080252|postscript=.|issue=2|url=https://zenodo.org/record/1425086}}</ref> The fusion of ideas from mathematics with those from chemistry began what has become part of the standard terminology of graph theory.

In particular, the term "graph" was introduced by [[James Joseph Sylvester|Sylvester]] in a paper published in 1878 in ''[[Nature (journal)|Nature]]'', where he draws an analogy between "quantic invariants" and "co-variants" of algebra and molecular diagrams:<ref name="Sylvester">{{cite journal | last1 = Sylvester | first1 = James Joseph | year = 1878 | title = Chemistry and Algebra | url = https://archive.org/stream/nature15unkngoog#page/n312/mode/1up | journal = Nature | volume = 17 | issue = 432| page = 284 | doi = 10.1038/017284a0 | bibcode = 1878Natur..17..284S | doi-access = free }}</ref>
:"[…] Every invariant and co-variant thus becomes expressible by a ''graph'' precisely identical with a [[August Kekulé|Kekuléan]] diagram or chemicograph. […] I give a rule for the geometrical multiplication of graphs, ''i.e.'' for constructing a ''graph'' to the product of in- or co-variants whose separate graphs are given. […]" (italics as in the original).

The first textbook on graph theory was written by [[Dénes Kőnig]], and published in 1936.<ref>{{citation|last1=Tutte|first1=W.T.|author-link=W. T. Tutte|title=Graph Theory|publisher=Cambridge University Press|year=2001|isbn=978-0-521-79489-3|page=30|url=https://books.google.com/books?id=uTGhooU37h4C&pg=PA30|access-date=2016-03-14}}</ref> Another book by [[Frank Harary]], published in 1969, was "considered the world over to be the definitive textbook on the subject",<ref>{{citation|page=203|title=Fractal Music, Hypercards, and more…Mathematical Recreations from Scientific American|first=Martin|last=Gardner|author-link=Martin Gardner|publisher=W. H. Freeman and Company|year=1992}}</ref> and enabled mathematicians, chemists, electrical engineers and social scientists to talk to each other. Harary donated all of the royalties to fund the [[George Pólya Prize|Pólya Prize]].<ref>{{citation|contribution=The George Polya Prize|url=http://www.siam.org/about/more/siam50.pdf|page=26|title=Looking Back, Looking Ahead: A SIAM History|author=Society for Industrial and Applied Mathematics|year=2002|access-date=2016-03-14|author-link=Society for Industrial and Applied Mathematics|archive-date=2016-03-05|archive-url=https://web.archive.org/web/20160305010030/http://www.siam.org/about/more/siam50.pdf|url-status=dead}}</ref>

One of the most famous and stimulating problems in graph theory is the [[four color problem]]: "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?" This problem was first posed by [[Francis Guthrie]] in 1852 and its first written record is in a letter of [[Augustus De Morgan|De Morgan]] addressed to [[William Rowan Hamilton|Hamilton]] the same year. Many incorrect proofs have been proposed, including those by Cayley, [[Alfred Kempe|Kempe]], and others. The study and the generalization of this problem by [[Peter Tait (physicist)|Tait]], [[Percy John Heawood|Heawood]], [[Frank P. Ramsey|Ramsey]] and [[Hugo Hadwiger|Hadwiger]] led to the study of the colorings of the graphs embedded on surfaces with arbitrary [[Genus (mathematics)|genus]]. Tait's reformulation generated a new class of problems, the ''factorization problems'', particularly studied by [[Julius Petersen|Petersen]] and [[Dénes Kőnig|Kőnig]]. The works of Ramsey on colorations and more specially the results obtained by [[Pál Turán|Turán]] in 1941 was at the origin of another branch of graph theory, ''[[extremal graph theory]]''.

The four color problem remained unsolved for more than a century. In 1969 [[Heinrich Heesch]] published a method for solving the problem using computers.<ref>Heinrich Heesch: Untersuchungen zum Vierfarbenproblem. Mannheim: Bibliographisches Institut 1969.</ref> A computer-aided proof produced in 1976 by [[Kenneth Appel]] and [[Wolfgang Haken]] makes fundamental use of the notion of "discharging" developed by Heesch.<ref name="AA1">{{Citation|author1=Appel, K. |author2=Haken, W.|title=Every planar map is four colorable. Part I. Discharging|journal=Illinois J. Math.|volume=21|issue=3|year=1977|pages=429–490|postscript=.|doi=10.1215/ijm/1256049011|doi-access=free|url=https://projecteuclid.org/journals/illinois-journal-of-mathematics/volume-21/issue-3/Every-planar-map-is-four-colorable-Part-I-Discharging/10.1215/ijm/1256049011.pdf}}</ref><ref name="AA2">{{Citation|author1=Appel, K. |author2=Haken, W.|title=Every planar map is four colorable. Part II. Reducibility|journal=Illinois J. Math.|volume=21|issue=3|year=1977|pages=491–567|postscript=.|doi=10.1215/ijm/1256049012|doi-access=free}}</ref> The proof involved checking the properties of 1,936 configurations by computer, and was not fully accepted at the time due to its complexity. A simpler proof considering only 633 configurations was given twenty years later by [[Neil Robertson (mathematician)|Robertson]], [[Paul Seymour (mathematician)|Seymour]], [[Daniel P. Sanders|Sanders]] and [[Robin Thomas (mathematician)|Thomas]].<ref name="RSST">{{Citation|author1=Robertson, N. |author2=Sanders, D. |author3=Seymour, P. |author4=Thomas, R. |title=The four color theorem|journal=Journal of Combinatorial Theory, Series B|volume=70|year=1997|pages=2–44|doi=10.1006/jctb.1997.1750|postscript=.|doi-access=free}}</ref>

The autonomous development of topology from 1860 and 1930 fertilized graph theory back through the works of [[Camille Jordan|Jordan]], [[Kazimierz Kuratowski|Kuratowski]] and [[Hassler Whitney|Whitney]]. Another important factor of common development of graph theory and [[topology]] came from the use of the techniques of modern algebra. The first example of such a use comes from the work of the physicist [[Gustav Kirchhoff]], who published in 1845 his [[Kirchhoff's circuit laws]] for calculating the [[voltage]] and [[Electric current|current]] in [[electric circuit]]s.

The introduction of probabilistic methods in graph theory, especially in the study of [[Paul Erdős|Erdős]] and [[Alfréd Rényi|Rényi]] of the asymptotic probability of graph connectivity, gave rise to yet another branch, known as ''[[Random graph|random graph theory]]'', which has been a fruitful source of graph-theoretic results.