Combinatorics & Graph Theory: Ramsey Theory, Four Color Theorem & Network Graphs
Encyclopedia/1. The Cosmos & The Natural World/1. Mathematics & Formal Systems/09. Graph Theory & Network Topology • Curated by Admin Timeline.sg
This timeline traces the development of combinatorics and graph theory from Euler's 1736 solution to the Königsberg bridge problem through the Four Color Theorem computer proof and the rise of network graph theory, highlighting key theorems and the probabilistic method.
Chronological Storyline (46 Milestones)
1736 CE
Euler Solves Königsberg Bridge Problem
Leonhard Euler publishes his solution to the Königsberg bridge problem, laying the foundations of graph theory. He introduces the concept of Eulerian paths and proves the impossibility of traversing each bridge exactly once. #graphtheory #math
Euler Solves Königsberg Bridge Problem By Twotwos - Own work based on: Konigsberg bridges.png. This file was derived from: Image-Koenigsberg, Map by Merian-Erben 1652.jpg, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=175193733
1847 CE
Kirchhoff Develops Circuit Laws
Gustav Kirchhoff publishes his laws for electrical circuits, using graph-theoretic concepts like spanning trees. His work is a precursor to network analysis. #graphtheory #physics
1852 CE
Four Color Conjecture Proposed
Francis Guthrie conjectures that four colors suffice to color any map on a sphere. The problem becomes one of the most famous in graph theory. #math #conjecture
Four Color Conjecture Proposed By Inductiveload - Based on a this raster image by chas zzz brown on en.wikipedia., CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=1680050
1856 CE
Hamilton Invents Icosian Game
William Rowan Hamilton invents the Icosian game, involving finding a Hamiltonian cycle on a dodecahedron. This leads to the concept of Hamiltonian paths in graph theory. #graphtheory #math
Hamilton Invents Icosian Game By Eyesinthefire - Own work - adapted from: by User:Janusz.c and styled after: by User:David Eppstein, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=187996031
1878 CE
Cayley Enumerates Trees
Arthur Cayley publishes a paper enumerating isomers of alkanes, leading to the formula for the number of labeled trees. His work is fundamental to combinatorial enumeration. #combinatorics #math
Cayley Enumerates Trees By Júlio Reis - Fully drawn by myself, after Cayley_graph_formula_2_4.gif by Rocchini, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=1699157
1879 CE
Kempe's Flawed Proof of Four Color Theorem
Alfred Kempe publishes a proof of the four color theorem, but it is later shown to be incorrect. His method of Kempe chains remains influential. #math #color
Kempe's Flawed Proof of Four Color Theorem By Unknown author - https://mathshistory.st-andrews.ac.uk/Biographies/Kempe/, Public domain, https://commons.wikimedia.org/w/index.php?curid=26768506
1890 CE
Heawood Finds Kempe's Error
Percy Heawood discovers a flaw in Kempe's proof of the four color theorem. He also proves the five color theorem and introduces the Heawood number for surfaces. #math #graph
Heawood Finds Kempe's Error By Cmglee - Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=110688489
1913 CE
Birkhoff Introduces Chromatic Polynomial
George David Birkhoff defines the chromatic polynomial of a graph in an attempt to solve the four color problem. This becomes a key tool in algebraic graph theory. #math #graph
Birkhoff Introduces Chromatic Polynomial By Thore Husfeldt (talk) - Own work (Original text: I created this work entirely by myself.), CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=31319868
1926 CE
Ramsey's Theorem Published Posthumously
Frank Plumpton Ramsey proves Ramsey's theorem, which states that in any coloring of a complete graph with two colors, a monochromatic subgraph of a given size cannot be avoided. This is the birth of Ramsey theory. #combinatorics #math
1931 CE
Menger's Theorem on Graph Connectivity
Karl Menger publishes his theorem characterizing graph connectivity, which is fundamental to network theory. It establishes the relationship between vertex separators and disjoint paths. #graph #network
1935 CE
Kőnig Publishes Graph Theory Text
Dénes Kőnig publishes 'Theorie der endlichen und unendlichen Graphen', the first comprehensive textbook on graph theory, solidifying the field. #graph #math
Kőnig Publishes Graph Theory Text By no conegut - BUDAPESTI MŰSZAKI ÉS GAZDASÁGTUDOMÁNYI EGYETEM MATEMATIKA INTÉZET: https://math.bme.hu/~hujter/konig1928.jpg, Public domain, https://commons.wikimedia.org/w/index.php?curid=90577639
1936 CE
Erdős–Ko–Rado Theorem
Paul Erdős, Chao Ko, and Richard Rado publish the Erdős–Ko–Rado theorem, which gives the maximum size of an intersecting family of subsets, a milestone in extremal combinatorics. #combinatorics #extremal
Erdős–Ko–Rado Theorem By David Eppstein - Own work, CC0, https://commons.wikimedia.org/w/index.php?curid=37039431
1941 CE
Brooks's Theorem on Graph Coloring
Rowland Leonard Brooks publishes Brooks's theorem, which gives a bound on the chromatic number of a graph in terms of its maximum degree. #graph #color
Brooks's Theorem on Graph Coloring By Vectorisation: BethNaught. Original: Claudio Rocchini (User:Rocchini) - This file was derived from: Graph exact coloring.gif This W3C-unspecified vector image was created with Inkscape ., CC BY 2.5, https://commons.wikimedia.org/w/index.php?curid=42831705
1946 CE
Tutte Develops Matroid Theory
William Thomas Tutte publishes his early work on matroids, unifying concepts from graph theory and linear algebra. His contributions to graph theory include the Tutte polynomial. #math #graph
1947 CE
Dijkstra's Algorithm for Shortest Paths
Edsger W. Dijkstra invents an efficient algorithm for finding shortest paths in graphs, a cornerstone of network routing. #algorithm #graph
Dijkstra's Algorithm for Shortest Paths By Ibmua - Work by uploader., Public domain, https://commons.wikimedia.org/w/index.php?curid=6282617
1950 CE
Probabilistic Method Introduced by Erdős
Paul Erdős introduces the probabilistic method with his paper on the existence of graphs with high chromatic number and large girth, revolutionizing combinatorics. #combinatorics #probabilistic
1954 CE
Ford–Fulkerson Algorithm for Max Flow
Lester Ford Jr. and Delbert Fulkerson publish the Ford–Fulkerson algorithm for computing maximum flow in a network, establishing the max-flow min-cut theorem. #network #math
1955 CE
Kruskal's Algorithm for Minimum Spanning Trees
Joseph Kruskal publishes an algorithm for finding the minimum spanning tree, a classic result in greedy algorithms. #algorithm #graph
Kruskal's Algorithm for Minimum Spanning Trees By Shiyu Ji - Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=54420893
1956 CE
Berge Introduces Perfect Graphs
Claude Berge introduces the concept of perfect graphs and formulates the strong perfect graph conjecture, a major open problem until its proof in 2002. #graph #math
Berge Introduces Perfect Graphs By David Eppstein - Own work, CC0, https://commons.wikimedia.org/w/index.php?curid=76325316
1957 CE
Tutte's Theorem on Perfect Matchings
William Tutte publishes his famous theorem characterizing graphs with perfect matchings, a key result in graph theory. #graph #matching
1959 CE
Erdős–Gallai Theorem on Graph Degree Sequences
Paul Erdős and Tibor Gallai publish a characterization of degree sequences of graphs, a fundamental tool in graph realizability. #graph #combinatorics
1960 CE
Kleitman Proves Erdős–Ko–Rado for Families with Intersection
Daniel Kleitman generalizes the Erdős–Ko–Rado theorem to intersecting families with additional structure, advancing extremal set theory. #combinatorics
1961 CE
Gallai–Hasse–Roy–Vitaver Theorem
The Gallai–Hasse–Roy–Vitaver theorem relates the chromatic number of a graph to the length of a longest directed path in an orientation, a duality result. #graph #color
Gallai–Hasse–Roy–Vitaver Theorem By David Eppstein - Own work, CC0, https://commons.wikimedia.org/w/index.php?curid=20521516
1963 CE
Hajnal–Szemerédi Theorem on Equitable Coloring
András Hajnal and Endre Szemerédi prove that any graph with maximum degree Δ has an equitable coloring with Δ+1 colors, a key result in graph coloring. #graph #combinatorics
1964 CE
Erdős–Simonovits Theorem on Extremal Graphs
Paul Erdős and Miklós Simonovits prove the Erdős–Simonovits theorem, which gives the extremal number for bipartite graphs, a central result in extremal graph theory. #graph #extremal
1965 CE
Pósa's Theorem on Hamiltonian Cycles
Lajos Pósa publishes a theorem giving sufficient conditions for the existence of Hamiltonian cycles, advancing the study of Hamiltonian graph theory. #graph #cycle
1968 CE
Lovász Proves Kneser's Conjecture
László Lovász proves Kneser's conjecture using topological methods, introducing the Borsuk–Ulam theorem into graph theory. #graph #topology
Lovász Proves Kneser's Conjecture By WatchduckYou can name the author as "T. Piesk", "Tilman Piesk" or "Watchduck"., Public domain, https://commons.wikimedia.org/w/index.php?curid=18609308
1970 CE
Lovász Local Lemma Published
László Lovász and Paul Erdős publish the Lovász local lemma, a powerful probabilistic tool for avoiding bad events in combinatorics. #combinatorics #probabilistic
1971 CE
Cook's Theorem on NP-Completeness
Stephen Cook proves the Cook–Levin theorem, establishing NP-completeness of the Boolean satisfiability problem, with implications for graph problems like Hamiltonian cycle. #complexity #computing
1972 CE
Karp Lists 21 NP-Complete Problems
Richard Karp publishes his seminal paper showing that 21 combinatorial problems, including graph problems like vertex cover and Hamiltonian cycle, are NP-complete. #complexity #graph
1973 CE
Tutte's Planar Graph Drawing Algorithm
William Tutte publishes an algorithm for drawing 3-connected planar graphs with straight lines and convex faces, using barycentric coordinates. #graph #drawing
Jun 1, 1976 CE
Appel and Haken Prove Four Color Theorem
Kenneth Appel and Wolfgang Haken announce a computer-assisted proof of the four color theorem, the first major theorem proven using computers. #math #computing
1977 CE
Szemerédi's Regularity Lemma
Endre Szemerédi proves the regularity lemma, a powerful tool for partitioning graphs into random-like pieces, with many applications in extremal combinatorics. #combinatorics #graph
Szemerédi's Regularity Lemma By Tristan Shin - http://yufeizhao.com/gtac, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=84482310
1978 CE
Robbins' Theorem on Strong Orientation
Herbert Robbins characterizes graphs that have a strongly connected orientation, known as Robbins' theorem, linking graph connectivity to network routing. #graph #network
1981 CE
Sperner's Lemma and Brouwer Fixed Point Theorem Link
The combinatorial Sperner's lemma is used to give a constructive proof of the Brouwer fixed point theorem, highlighting connections between combinatorics and topology. #combinatorics #topology
Sperner's Lemma and Brouwer Fixed Point Theorem Link By Unknown author, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=1242404
1983 CE
Graph Minors Theory Initiated by Robertson and Seymour
Neil Robertson and Paul Seymour begin their monumental series on graph minors, eventually proving Wagner's conjecture and developing deep structural graph theory. #graph #theory
1984 CE
Karmarkar's Interior Point Method for Linear Programming
Narendra Karmarkar introduces a polynomial-time interior point method for linear programming, which has applications in network flow optimization. #optimization #algorithm
1986 CE
Alon and Tarsi on Combinatorial Nullstellensatz
Noga Alon and Michael Tarsi develop the Combinatorial Nullstellensatz, a powerful algebraic method for graph coloring and combinatorial problems. #combinatorics #algebra
1990 CE
Robertson–Seymour Theorem Proved
Neil Robertson and Paul Seymour complete their proof of Wagner's conjecture, stating that any infinite set of graphs contains one that is a minor of another. This is a landmark in structural graph theory. #graph #minor
1993 CE
Hales–Jewett Theorem Generalized
The Hales–Jewett theorem, a combinatorial result about tic-tac-toe-like games, is generalized, influencing extremal combinatorics and Ramsey theory. #combinatorics #Ramsey
1995 CE
Szemerédi–Trotter Theorem in Incidence Geometry
Endre Szemerédi and William Trotter prove a theorem on the maximum number of point-line incidences, with applications to combinatorial geometry and graph drawing. #geometry #combinatorics
1996 CE
Ajtai–Komlós–Szemerédi on Circuit Complexity
Miklós Ajtai, János Komlós, and Endre Szemerédi prove a lower bound for sorting networks, using graph-theoretic methods. #complexity #sorting
Ajtai–Komlós–Szemerédi on Circuit Complexity By --Oskar - Own work (Original text: self-made), CC BY 3.0, https://commons.wikimedia.org/w/index.php?curid=5840643
1997 CE
Kleinberg's HITS Algorithm for Web Search
Jon Kleinberg proposes the HITS algorithm (Hyperlink-Induced Topic Search) for ranking web pages based on link structure, a foundational graph algorithm. #network #web
1998 CE
Watts–Strogatz Model of Small-World Networks
Duncan Watts and Steven Strogatz publish a model for small-world networks, combining high clustering and short path lengths, sparking interest in network science. #network #graph
Watts–Strogatz Model of Small-World Networks By The Opte Project - Originally from the English Wikipedia; description page is/was here., CC BY 2.5, https://commons.wikimedia.org/w/index.php?curid=1538544
1999 CE
Barabási–Albert Model of Scale-Free Networks
Albert-László Barabási and Réka Albert propose the Barabási–Albert model for scale-free networks, showing preferential attachment leads to power-law degree distributions. #network #graph
2000 CE
PageRank Algorithm Patented
Larry Page and Sergey Brin patent PageRank, the algorithm behind Google's web search, which uses graph theory to rank pages based on link structure. #network #search
PageRank Algorithm Patented By Sage santo - Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=153695322
