From Konigsberg's Bridges to Complex Networks: A Narrative Review of Graph Theory's Foundations, Landmark Theorems, and Applications

Abstract

Graph theory began in 1736 as Euler's solution to the Konigsberg bridge problem and became mathematics' most versatile language for structure---in chemistry, sociology, computer science, and network science. This article presents a narrative review of the field's canonical line: Euler's 1736 paper, Kempe's 1879 four-color attempt, Konig's 1936 founding treatise, Erdos and Renyi's random graphs, Dirac's 1952 Hamiltonian theorem, the Appel--Haken four-color proof, Watts and Strogatz's small worlds, Barabási and Albert's scale-free networks, the Graph Minors program's completion by Robertson and Seymour, and the modern textbooks of Harary, Bondy and Murty, and Diestel. The synthesis is organized around three themes: foundations, in which graphs were formalized and their central problems---coloring, connectivity, traversability---defined; structure, in which random, small-world, and scale-free models quantified real networks; and depth, in which the Graph Minors program demonstrated the field's modern combinatorial power. It is concluded that graph theory's history is the refinement of a single idea---structure abstracted from substance---whose applications now feed back into the mathematics itself.