← 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.
| aliases | Graph theory |
| born at | 1735-1736 (presented 26 August 1735) |
| born precision | about a year; printed 1741 |
| boundary | Inside: 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 level | A 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. |
| scale | social |
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 correction | 5 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 time | over 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) bounds | 43 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 K4 | 2 among 6.4 × 10^22 colourings |
| diagonal Ramsey upper bound | R(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 bound | exp((log n)^O(1)) (quasipolynomial) time |
| Web size read in 1999 | over 800 million vertices |
| degree exponent of the Web's in-links | 2.1 ± 0.1 gamma |
| degree exponent of the movie-actor collaboration graph | 2.3 ± 0.1 gamma |
| western US power grid | 4941 vertices; gamma about 4 |
| network data sets tested for scale-free structure | nearly 1000 data sets |
| share with the strongest evidence of scale-free structure | 4 % |
| share with the weakest evidence of scale-free structure | 52 % |
| giant component threshold in the Poisson random graph | z = 1 mean degree |
| connectivity threshold of G(n,p) | ln n / n edge probability |
| Milgram letters reaching the target | about 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 reconstructed | 282 neurons |
| Petersen graph automorphisms | 120 elements (the symmetric group S5) |
| Koenigsberg bridges at Euler's sites today | 5 of 7 bridges |
Open contentions (7) open contention
Where sources or readings disagree. Both stay on the map.
- C-392 Are 'scale-free' networks rare or everywhere?
booked: The map keeps both: strict scale-free structure is rare across 928 data sets, while heavy-tailed connections are very common.
the other reading: power laws universal for growing networks; power laws a poor model of most real degree distributions - C-413 Where do thoughts come from?
booked: No theory is proven, so the map lists the main ones side by side and doesn't pick one. It shows where thinking is handled in the brain, not where thoughts start.
the other reading: see C-413 (thought origin) - C-1364 Is the Internet fragile to targeted attack?
booked: The map keeps both: the finding that such networks shrug off random failures but break under targeted attack, and the reply that the real router network isn't built that way.
the other reading: router-level Internet not scale-free in that sense (C-1364) - C-1528 Can a computer virus die out on its own?
booked: The map keeps both readings: a spread threshold below which outbreaks die, and networks with no such threshold where viruses linger at low levels.
the other reading: threshold epidemics (C-1528) - C-3254 How many configurations did the four colour proof need?
booked: The map keeps the competing readings; none is ruled.
the other reading: the counts may refer to different stages or versions of Appel and Haken's proof; the primary papers (Illinois J. Math. 1977) were not reached - C-3258 When was graph theory born: 1735, 1736 or 1741?
booked: The map keeps the competing readings; none is ruled.
the other reading: printed in 1741 in the Commentarii (src:wp:seven-bridges-of-konigsberg); Newman 2003 dates the solution 1735; Leibniz's analysis situs and Vandermonde's knight's tour (1771) as forerunners; Kőnig's 1936 textbook as the start of the field as a field - C-3259 Is graph theory its own field or part of combinatorics?
booked: The map keeps the competing readings; none is ruled.
the other reading: a part of combinatorics ('often considered part of combinatorics')
Partners and parts published science
Built from / builds (11)
- Combinatorics: the practice of counting, arranging and choosing finite structures (permutations, combinations, partitions, designs, graphs), the structures it studies, and the people and machines who work with them
- Random graph (Erdős-Rényi)
- Ramsey theory
- Graphs (vertices and edges), the structure studied
- Topological graph theory
- Algebraic graph theory (spectral graph theory, graph symmetry)
- Geometric graph theory and graph drawing
- Extremal graph theory
- Graph colouring (the four colour problem and its descendants)
- Graph theorists and their collaborations (the practitioners)
- Textbooks (Kőnig 1936, Harary 1969)
Sits inside / holds (3)
- Mathematics (the field: the practice and the structures it studies)
- Computer science (the field: the practice and the computation it studies)
- Combinatorics: the practice of counting, arranging and choosing finite structures (permutations, combinations, partitions, designs, graphs), the structures it studies, and the people and machines who work with them
Trades with (valence) (20)
- Combinatorics: the practice of counting, arranging and choosing finite structures (permutations, combinations, partitions, designs, graphs), the structures it studies, and the people and machines who work with them via sys:written-record · Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on gain
- Human (Homo sapiens) via sys:sensory-environment · Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on gain
- Internet via sys:sensory-environment · Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on gain
- Chemistry (the field: the practice of chemists and the structure of substances and their reactions it works on) via sys:written-record · Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on gain
- Human brain via sys:sensory-environment · Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on gain
- Hippocampus (memory) via sys:mental-representation · Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on gain
- Complex network (scale-free growth, preferential attachment, small worlds; walked as an idea) via sys:written-record · Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on gain
- Social network via sys:sensory-environment · Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on gain
- Mathematics (the field: the practice and the structures it studies) via sys:written-record · Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on gain
- Map (maps and map-making) via sys:sensory-environment · Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on gain
- Computer via sys:computer-hardware · Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on gain
- Probability: weighing chances, in brains and in people's mathematics, and the structure it works on via sys:written-record · Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on gain
- Linear algebra (the practice of solving, transforming and taking apart linear systems with vectors and matrices, and the structures it works with) via sys:written-record · Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on gain
- Electric circuit via sys:mental-representation · Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on gain
- Proof assistant (Metamath, Lean, Isabelle and the like) via sys:computer-hardware · Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on gain
- Topology (set-theoretic topology) via sys:written-record · Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on gain
- Computer science (the field: the practice and the computation it studies) via sys:written-record · Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on gain
- Mathematical proof: the practice of showing that a statement follows from axioms and earlier theorems, how it is written, checked (by people and machines) and accepted, and the derivations it works on via sys:written-record · Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on gain
- Prime numbers (the practice of number theory that finds, proves and uses them, and the structure of the primes it works on) via sys:sensory-environment · Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on even
- Network (the general system of things joined by links) via sys:sensory-environment · Graph theory: the practice of studying vertices joined by edges (problems, proofs, algorithms, its people and books) and the graphs it works on gain
expressed by (17)
- Generation/Synthesis
- Recombination/Composition
- Scaffolding/Enablement (Meta-Tooling)
- Templating / Standardization
- Interoperability/Transduction (Bridging)
- Encapsulation & Modularity (Abstraction)
- Symbiosis/Co-Creation (Collaborative Specialization)
- Sensing/Scanning
- Hypothesis/Goal Selection
- Mapping/Modeling
- Uncertainty Reduction/Learning
- Active Experimentation / Probing (Optimal Experimental Design)
- Trail-Marking / Externalized Memory (Stigmergy)
- Technique-Based Identification (a.k.a. Technique-Based Detection)
- Validation of Effectiveness
- Resilience & Repair
- Quality Control & Error Correction
floor filled by (25)
- Combinatorics: the practice of counting, arranging and choosing finite structures (permutations, combinations, partitions, designs, graphs), the structures it studies, and the people and machines who work with them
- Human (Homo sapiens)
- Chemistry (the field: the practice of chemists and the structure of substances and their reactions it works on)
- Human brain
- Hippocampus (memory)
- Complex network (scale-free growth, preferential attachment, small worlds; walked as an idea)
- Random graph (Erdős-Rényi)
- Mathematics (the field: the practice and the structures it studies)
- Map (maps and map-making)
- Computer
- Proof assistant (Metamath, Lean, Isabelle and the like)
- Computer science (the field: the practice and the computation it studies)
- Mathematical proof: the practice of showing that a statement follows from axioms and earlier theorems, how it is written, checked (by people and machines) and accepted, and the derivations it works on
- Adjacency matrix
- Ramsey theory
- Graphs (vertices and edges), the structure studied
- Topological graph theory
- Algebraic graph theory (spectral graph theory, graph symmetry)
- Extremal graph theory
- Graph colouring (the four colour problem and its descendants)
- Graph theorists and their collaborations (the practitioners)
- Textbooks (Kőnig 1936, Harary 1969)
- Network (the general system of things joined by links)
- Graph drawing
- Seven Bridges of Königsberg
represents (1)
Kinds (3)
Notes published science
- The Koenigsberg puzzle Euler proved impossible became possible: bombing in World War II and later rebuilding left five bridges at Euler's sites, and now a walk crossing each once exists, starting on one island and ending on the other (src:wp:seven-bridges-of-konigsberg).
- You learn networks without knowing it: shown items in a sequence, people's brains build a map-like picture of which items are linked, in the same hippocampal-entorhinal system that maps space, even when the links are 'unavailable to conscious awareness' (src:garvert-2017; src:schapiro-2013).
- An 88-year-old bound fell: Erdős and Szekeres showed in 1935 that every two-colouring of 4^k points hides a one-colour group of k; the first exponential improvement, (4 − ε)^k, came only in 2023, while the exact value for k = 5 is still somewhere between 43 and 46 (src:campos-2023-ramsey; src:wp:ramseys-theorem).
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)
- 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
- L2: Taking it in: drawings (dots and lines), tables (edge lists, adjacency matrices) and data sets gathered from the sciences
- 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
- L4: Problems, examples and conjectures: walks crossing every edge once, colourings, trees, cliques, isomorphism, Ramsey numbers, random graphs
- L5: Proof and computation: theorems proved by people, cases checked by computer, algorithms and their running times; claims checked by colleagues
- L6: The body of theory: subareas (topological, algebraic, geometric, extremal, random graphs, enumeration), textbooks and a shared terminology
- 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)
- L4: Problems, examples and conjectures: Euler's walk question, the four colour problem, Ramsey numbers, graph isomorphism, random graphs; open problems set the work
- L5: Proof and computation: theorems proved, cases checked by computer, algorithms bounded; claims checked by colleagues and by a proof assistant's kernel
- L6: The body of theory: subareas, textbooks and a shared terminology
- L7: Understanding and use: graph methods handed to the sciences and to technology
way in: Colleagues: collaborators, announcements and the checking of claims
- L1: Collaboration ties: two scientists joined if they have written a paper together
- L2: A claim announced to colleagues (Babai's lectures of November 2015)
- L3: Checked by others: a flaw found, the claim cut back, then repaired and confirmed
- L4: Acceptance and dispute: a computer-assisted proof met with controversy
way in: Machines: graphs stored, searched and checked by computer
- L1: Graphs held in a computer
- L2: Data structures: edge lists and adjacency lists for sparse graphs, matrices for fast access
- L3: Exhaustive search and generation: every 2-colouring of a small complete graph examined; graphs generated by different routes
- 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)
- L1: Connected systems: genes and proteins, nerve cells and axons, people and organisations, web pages and links
- L2: Data gathered: questionnaires, databases, robots crawling the Web; since the 1990s computerised acquisition of large networks
- 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)
- L1: Items arriving in sequence: words in language, notes in music, concepts in books, pages on the Internet
- L2: Transitions between items noticed: fine-scale structure, the probabilities of going from one item to the next
- 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)
- L1: Drawn graphs: a point or circle for each vertex, a line for each edge, arrows for direction
- L2: Seeing the layout: some layouts read more easily than others; crossings, symmetry and area matter to the reader
- L3: From drawing to graph: only which vertices are joined, and how many times, is kept
way in: The written record: papers, textbooks, terminology
- L1: Papers and books: Euler's memoir, Sylvester's 1878 note, Kőnig's 1936 textbook, Harary's 1969 book, arXiv preprints
- L2: Reading definitions, which vary from author to author
- L3: A shared vocabulary, partly taken from chemistry
way in: Thought: relational knowledge held as a map (inner)
- L1: Relations among objects met in experience, non-spatial and discrete
- 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
- L1: The program running on stored graphs
- L5: An algorithm whose cost scales with the graph
- L7: Route planning, register allocation, learning on graph-structured data
way out: Graph models handed to the sciences
- L1: Back on the world: what is targeted, protected or rebuilt in the network
- L3: Measures computed on the system's graph: degree, clustering, betweenness, modules, rich clubs
- L7: A science takes graph methods up for its own system (connectomics, molecular biology, chemistry)
way out: Papers and textbooks
- L1: The paper or book in the record
- L6: Results chosen and organised for readers; Harary's textbook let several fields talk
way out: Teaching: textbooks and courses
- L1: The book in readers' hands
- L6: The field gathered into a textbook
Sources (25) published science
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)
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)