Proving four colours suffice for any map took a century and a computer
In 1852 Francis Guthrie asked whether four colours are always enough to paint a map so that neighbouring regions differ. Mathematicians offered wrong proofs for over a hundred years. In 1976 Kenneth Appel and Wolfgang Haken finally settled it by having a computer check 1,936 configurations, a proof many refused to accept at first.
Graph theory studies networks of vertices joined by edges, used to model pairwise relationships. Edges may be undirected or directed with arrows, some graphs mix both, and weighted graphs attach numbers to edges. Though often filed under combinatorics, the subject has grown into a field of its own. James Joseph Sylvester introduced the term in an 1878 paper in Nature, comparing algebraic invariants with molecular diagrams.
Its founding document is Leonhard Euler's 1736 paper on the Seven Bridges of Königsberg. Alexandre-Théophile Vandermonde followed in 1771 with work on the knight's tour, both extending an idea of Leibniz's called analysis situs, and Euler's formula linking the vertices, edges and faces of a polyhedron helped launch topology. A century later Arthur Cayley studied trees, a special class of graphs, with consequences for chemistry, and George Pólya's results of 1935 to 1937 built enumerative graph theory. Gustav Kirchhoff's 1845 circuit laws were an early use of algebraic methods.
Dénes Kőnig wrote the first textbook in 1936. Frank Harary's 1969 book became the standard reference that let mathematicians, chemists, engineers and social scientists share a language, and he gave its royalties to fund the Pólya Prize. The four colour problem, first written down in a letter from Augustus De Morgan to William Rowan Hamilton, drove much research; Heinrich Heesch proposed a computer approach in 1969 using an idea called discharging that Appel and Haken later relied on.
Modern branches abound. Paul Erdős and Alfréd Rényi founded random graph theory by studying the probability that a graph is connected. Wagner's theorem says a graph can be drawn flat without crossings exactly when it does not contain the complete graph on five vertices or the utility graph as a minor. Pál Turán's question about minimising crossings between tracks from brick kilns to storage sites began the study of crossing numbers. Spectral graph theory analyses eigenvalues of adjacency matrices, and Frucht's theorem shows every finite group is the symmetry group of some graph.
Source: Graph theory
