Research work · 2026
Points and Lines: A Narrative Review of Graph Theory from Euler's Bridges to Random Graphs and Modern Structure
Zenodo (CERN European Organization for Nuclear Research)
Abstract
Graph theory---the mathematics of relationships among discrete objects---was born in a puzzle about bridges and matured into network science's foundation. This article presents a narrative review of the field's canonical line: Euler's 1736 Konigsberg solution, Kirchhoff's 1847 matrix tree theorem, Cayley's 1857 trees, Ramsey's 1930 theorem, Turan's 1941 extremal graphs, Konig's 1936 first treatise, Berge's 1958 theory, Erdos and Renyi's 1959 random graphs, Harary's 1969 synthesis, Bondy and Murty's applications, West's and Diestel's modern texts. The synthesis is organized around three themes: combinatorial structure, in which paths, trees, and colorings formalized connectivity and constraints; extremality and randomness, in which Ramsey, Turan, and the Erdos-Renyi model quantified order's thresholds; and modernity, in which algorithms, probabilistic method, and network science carried the bridges' puzzle into infrastructure and society. It is concluded that graph theory exemplifies mathematics' trajectory from recreational puzzle to structural science---and that its language now describes everything from molecules to markets.