EVOPEDIA

← all systems · see it in The System

Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on

In mathematics and computer science, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.

Properties published scienceour proposal

Sourced fields, and our own readings.

aliasesGraph theory
born at1735-1736 (presented 26 August 1735)
born precisionabout a year; printed 1741
boundaryInside: the practice of graph theory (posing problems about vertices and edges, drawing and tabling graphs, exploring examples, conjecturing, proving, computing and checking, organising results into subareas, teaching them) with the people, books and machines that carry it, and the structure it works on (graphs: vertices joined by edges, directed or not, weighted or not, finite or infinite), booked in roles. Outside: the connected systems it models (brains, molecules, societies, the Web, power grids), the sciences that use its models (network science, chemistry, connectomics, computer science), and the rest of mathematics it borrows from (algebra, topology, probability).
nested levelA field of mathematics (part inside a whole: 'part of discrete mathematics, often considered part of combinatorics, although it is a stand-alone field'). It runs on people (their sight of drawings, their learning of relations from sequences, their relational maps in the hippocampal-entorhinal system), on its written record and, since 1976, on computers. The graphs it studies are booked as structure in roles.
scalesocial

Measures (29) published science

characteristic clock: four colour conjecture to proof (1852 to 1976)124 years (derived from two dates the sources give)
characteristic clock: Erdős–Szekeres Ramsey upper bound to its first exponential improvement (1935 to 2023)88 years (derived)
characteristic clock: graph isomorphism claim retraction to correction5 days (4 to 9 January 2017)
false proof standing time (Kempe, Tait)11 years
four colour proof: reducible configurations checked by computer (Four color theorem page)1,834 (later 1,482) configurations
four colour proof: configurations (Graph theory page)1,936 configurations
four colour proof: computer timeover a thousand hours
four colour re-proof (Robertson, Sanders, Seymour, Thomas 1997)633 configurations
Ramsey number R(4,4)18 vertices
Ramsey number R(5,5) bounds43 to 46 vertices (inclusive)
(5,5,42) graphs found by computer (McKay, Radziszowski, Exoo 1997)656 graphs
2-colourings of a 16-vertex complete graph with no monochromatic K42 among 6.4 × 10^22 colourings
diagonal Ramsey upper boundR(k) ≤ (4 − ε)^k for some ε > 0 (was 4^k) vertices
graph isomorphism: best previous bound (Luks 1983)exp(O(√(n log n))) time, n vertices
graph isomorphism: Babai's boundexp((log n)^O(1)) (quasipolynomial) time
Web size read in 1999over 800 million vertices
degree exponent of the Web's in-links2.1 ± 0.1 gamma
degree exponent of the movie-actor collaboration graph2.3 ± 0.1 gamma
western US power grid4941 vertices; gamma about 4
network data sets tested for scale-free structurenearly 1000 data sets
share with the strongest evidence of scale-free structure4 %
share with the weakest evidence of scale-free structure52 %
giant component threshold in the Poisson random graphz = 1 mean degree
connectivity threshold of G(n,p)ln n / n edge probability
Milgram letters reaching the targetabout a quarter, through about six people fraction; hand-offs
per-hand-off delivery in Milgram's chain (derived)about 0.79 fraction delivered per hand-off: 0.25^(1/6), derived from 'about a quarter' over 'about six'
C. elegans neural network reconstructed282 neurons
Petersen graph automorphisms120 elements (the symmetric group S5)
Koenigsberg bridges at Euler's sites today5 of 7 bridges

Open contentions (7) open contention

Where sources or readings disagree. Both stay on the map.

Partners and parts published science

Built from / builds (11)

Sits inside / holds (3)

Trades with (valence) (20)

expressed by (17)

floor filled by (25)

represents (1)

Kinds (3)

Notes published science

Layers

The ways it takes in its world, where they meet, and how it acts back, each from L1 (where it meets the world) up.

graph theory as mathematicians describe it: things joined in pairs in the world, drawn or tabled as dots and lines, abstracted to vertices and edges, explored for paths, colourings, trees and random structure, proved and computed, gathered into theory and handed back to every field that maps connections (reader's view)

  1. L1: Things joined in pairs in the world: land masses and bridges, atoms and bonds, people and ties, pages and links, neurons and synapses, power stations and lines
  2. L2: Taking it in: drawings (dots and lines), tables (edge lists, adjacency matrices) and data sets gathered from the sciences
  3. L3: The abstraction: a graph, vertices joined by edges, kept apart from any drawing of it; directed or undirected, simple or multi, weighted or not
  4. L4: Problems, examples and conjectures: walks crossing every edge once, colourings, trees, cliques, isomorphism, Ramsey numbers, random graphs
  5. L5: Proof and computation: theorems proved by people, cases checked by computer, algorithms and their running times; claims checked by colleagues
  6. L6: The body of theory: subareas (topological, algebraic, geometric, extremal, random graphs, enumeration), textbooks and a shared terminology
  7. L7: Use: graph models and algorithms handed to network science, connectomics, molecular biology, chemistry, sociology, linguistics, computer science and route planning

the boardroom (shared floors)

  1. L4: Problems, examples and conjectures: Euler's walk question, the four colour problem, Ramsey numbers, graph isomorphism, random graphs; open problems set the work
  2. L5: Proof and computation: theorems proved, cases checked by computer, algorithms bounded; claims checked by colleagues and by a proof assistant's kernel
  3. L6: The body of theory: subareas, textbooks and a shared terminology
  4. L7: Understanding and use: graph methods handed to the sciences and to technology

way in: Colleagues: collaborators, announcements and the checking of claims

  1. L1: Collaboration ties: two scientists joined if they have written a paper together
  2. L2: A claim announced to colleagues (Babai's lectures of November 2015)
  3. L3: Checked by others: a flaw found, the claim cut back, then repaired and confirmed
  4. L4: Acceptance and dispute: a computer-assisted proof met with controversy

way in: Machines: graphs stored, searched and checked by computer

  1. L1: Graphs held in a computer
  2. L2: Data structures: edge lists and adjacency lists for sparse graphs, matrices for fast access
  3. L3: Exhaustive search and generation: every 2-colouring of a small complete graph examined; graphs generated by different routes
  4. L4: Case checking for a proof: the four colour theorem's reducible configurations checked one by one

way in: Problems and data from the connected world (the sciences' networks)

  1. L1: Connected systems: genes and proteins, nerve cells and axons, people and organisations, web pages and links
  2. L2: Data gathered: questionnaires, databases, robots crawling the Web; since the 1990s computerised acquisition of large networks
  3. L3: Encoded as a graph: the measurer chooses what the nodes and edges are (a neuron or a brain region; binary or weighted, directed or not)

way in: Sequences: learning a network from items met one after another (sight and hearing over time)

  1. L1: Items arriving in sequence: words in language, notes in music, concepts in books, pages on the Internet
  2. L2: Transitions between items noticed: fine-scale structure, the probabilities of going from one item to the next
  3. L3: Communities in the network felt as events: representations gather around clusters of mutually predicting items, in left inferior frontal gyrus, anterior temporal lobe, insula and superior temporal gyrus

way in: Sight: drawings of dots and lines (node-link diagrams)

  1. L1: Drawn graphs: a point or circle for each vertex, a line for each edge, arrows for direction
  2. L2: Seeing the layout: some layouts read more easily than others; crossings, symmetry and area matter to the reader
  3. L3: From drawing to graph: only which vertices are joined, and how many times, is kept

way in: The written record: papers, textbooks, terminology

  1. L1: Papers and books: Euler's memoir, Sylvester's 1878 note, Kőnig's 1936 textbook, Harary's 1969 book, arXiv preprints
  2. L2: Reading definitions, which vary from author to author
  3. L3: A shared vocabulary, partly taken from chemistry

way in: Thought: relational knowledge held as a map (inner)

  1. L1: Relations among objects met in experience, non-spatial and discrete
  2. L3: A map-like structure of the relations in the hippocampal-entorhinal cortex, weighted by associative strength, without awareness

way out: Algorithms run on machines

  1. L1: The program running on stored graphs
  2. L5: An algorithm whose cost scales with the graph
  3. L7: Route planning, register allocation, learning on graph-structured data

way out: Graph models handed to the sciences

  1. L1: Back on the world: what is targeted, protected or rebuilt in the network
  2. L3: Measures computed on the system's graph: degree, clustering, betweenness, modules, rich clubs
  3. L7: A science takes graph methods up for its own system (connectomics, molecular biology, chemistry)

way out: Papers and textbooks

  1. L1: The paper or book in the record
  2. L6: Results chosen and organised for readers; Harary's textbook let several fields talk

way out: Teaching: textbooks and courses

  1. L1: The book in readers' hands
  2. L6: The field gathered into a textbook

Sources (25) published science

Graph theory (Wikipedia, via Wikimedia Enterprise snapshot 2026-11-01)
Four color theorem (Wikipedia, via Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Graph isomorphism problem (Wikipedia, via Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Barabási A-L, Albert R. Emergence of scaling in random networks. Science 286:509 (1999); arXiv:cond-mat/9910332 (behind its links)
Holroyd AE, Levine L, Mészáros K, Peres Y, Propp J, Wilson DB. Chip-firing and rotor-routing on directed graphs. In and Out of Equilibrium 2 (2008); arXiv:0801.3306 v4 (behind its links)
Newman MEJ. The structure and function of complex networks. SIAM Review 45:167 (2003); arXiv:cond-mat/0303516 (behind its links)
Graph coloring (Wikipedia, via Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Campos M, Griffiths S, Morris R, Sahasrabudhe J. An exponential improvement for diagonal Ramsey. arXiv:2303.09521 (v2 2025) (behind its links)
Ramsey's theorem (Wikipedia, via Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Babai L. Graph isomorphism in quasipolynomial time. arXiv:1512.03547 (2nd preliminary version, 19 Jan 2016) (behind its links)
Broido and Clauset, Scale-free networks are rare, Nat. Commun. 10 (2019), doi:10.1038/s41467-019-08746-5 (PMC6399239) (behind its links)
Erdős–Rényi model (Wikipedia, via Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Seven Bridges of Königsberg (Wikipedia, via Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Newman MEJ. The structure of scientific collaboration networks. PNAS 98:404 (2001). doi:10.1073/pnas.98.2.404 (behind its links)
Combinatorics (Wikipedia, via Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Sporns O. Graph theory methods: applications in brain networks. Dialogues in Clinical Neuroscience 20:111 (2018). doi:10.31887/DCNS.2018.20.2/osporns (behind its links)
Lynn CW, Bassett DS. How humans learn and represent networks. PNAS 117:29407 (2020). doi:10.1073/pnas.1912328117 (behind its links)
Garvert MM, Dolan RJ, Behrens TEJ. A map of abstract relational knowledge in the human hippocampal-entorhinal cortex. eLife 6:e17086 (2017). doi:10.7554/eLife.17086 (behind its links)
Paley graph (Wikipedia, via Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Green B, Tao T. The primes contain arbitrarily long arithmetic progressions. arXiv:math/0404188 (Annals of Mathematics 167 (2008) 481-547) (behind its links)
Schapiro AC, Rogers TT, Cordova NI, Turk-Browne NB, Botvinick MM. Neural representations of events arise from temporal community structure. Nature Neuroscience 16:486 (2013). doi:10.1038/nn.3331 (author manuscript) (behind its links)
Dénes Kőnig (Wikipedia, via Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Pavlopoulos GA et al. Using graph theory to analyze biological networks. BioData Mining 4:10 (2011). doi:10.1186/1756-0381-4-10 (behind its links)
Kipf TN, Welling M. Semi-supervised classification with graph convolutional networks. ICLR 2017; arXiv:1609.02907 (behind its links)
Network science (Wikipedia, via Wikimedia Enterprise snapshot 2026-11-01) (behind its links)