- Atlas
- Mathematics
- Graph Theory
Graph Theory
Graph theory is the study of graphs: finite collections of points, called vertices, joined in pairs by lines, called edges.
10 frameworks, from 1736 to today · Combinatorics · Mathematics
- Eulerian foundations 1736-Present
- Graph coloring 1852-Present
- Graph enumeration 1857-Present
- Algebraic graph theory 1930-Present
- Extremal graph theory 1941-Present
- Algorithmic and combinatorial optimisation on graphs 1950-Present
- Random graph 1959-Present
- Structural graph theory and graph minors 1980-Present
- Network science 1998-Present
- Graphon 2000-Present
Overview
Graph theory is the study of graphs: finite collections of points, called vertices, joined in pairs by lines, called edges. A road map, a family tree, a friendship network, and a molecule can all be drawn this way, and the same abstract object answers questions about all of them. What is at stake is a kind of structure that is simpler than geometry—no distances, no angles, only who is connected to whom—yet rich enough to pose some of the hardest problems in mathematics. The field's history is a long movement from puzzles about drawing and travelling, through a nineteenth-century phase of maps and molecules, to a modern discipline with algebraic, probabilistic, algorithmic, and extremal branches that feed directly into computer science, chemistry, and the study of real networks.
Bridges, circuits, and the birth of an idea
The founding episode is Leonhard Euler's 1736 treatment of the Königsberg bridges123. The city's river divided land into four regions connected by seven bridges, and the question was whether a walk could cross each bridge exactly once and return to the start. Euler's insight was that the geography was irrelevant; only the pattern of connections mattered. He reasoned that every region entered on a walk must also be left, so each region must touch an even number of bridges—except possibly the start and end3. Since all four regions of Königsberg touched an odd number, no such walk existed. In doing so he isolated the concept of a graph and the notion of a circuit (a closed route using each edge once), and he proved the general criterion: such a circuit exists exactly when the graph is connected and every vertex has even degree (the number of edges meeting it). This is still called an Eulerian circuit, and the argument is the model for the whole style of the subject—translate a concrete situation into vertices and edges, then find the structural condition that decides it.
For roughly a century afterward the subject grew in scattered pieces rather than as a recognised field. In 1847 Gustav Kirchhoff used graphs—trees, in effect—to analyse electrical networks, showing that the currents in a circuit are governed by the structure of its cycles. In 1857 Arthur Cayley, studying the counting of chemical isomers, enumerated the trees (connected graphs with no cycles) with a given number of vertices, and the word "tree" for such a structure entered mathematics. These were applications that happened to use graph-like reasoning; there was not yet a community calling itself graph theorists.
Colouring, maps, and the four-colour problem
The question that did most to create the field was posed in 1852, when Francis Guthrie noticed that a map of English counties seemed to need only four colours so that neighbouring regions differed14. The four-colour conjecture—that every planar map can be coloured with four colours—became a public mathematical obsession15. It forced mathematicians to define precisely what a planar graph is (one drawable in the plane without edges crossing) and to develop the machinery of colouring: assigning labels to vertices so that adjacent vertices get different labels, with the chromatic number being the fewest labels needed146.
Progress came in stages. In 1879 Alfred Kempe published a purported proof that stood for eleven years before Percy Heawood found a flaw; Heawood salvaged the method to prove that five colours always suffice (1890)4. The four-colour problem resisted until 1976, when Kenneth Appel and Wolfgang Haken proved it with a computer-assisted case analysis—the first major theorem whose proof no human could check by hand, a landmark in the relationship between mathematics and computation145. Alongside this, the study of colouring grew into a subject in its own right, with results such as the 1912 theorem of George Birkhoff on chromatic polynomials (a polynomial whose values count the colourings of a graph) and the general theory of when graphs are bipartite (two-colourable) or require many colours478.
Enumeration and the counting of structures
A parallel strand asked how many graphs of a given kind exist19. Cayley's tree counts were extended by many hands; a striking formula, now usually credited to Cayley (1889), states that there are $n^{n-2}$ labelled trees on $n$ vertices. The general problem of counting graphs, connected graphs, and graphs with prescribed properties became enumerative graph theory, and it developed its own tools: generating functions, recurrence relations, and later the powerful method of Pólya (1937) for counting objects up to symmetry19. Enumeration was not idle bookkeeping—it supplied the raw material for probability, since knowing how many graphs exist lets one ask what a typical one looks like.
The probabilistic turn
That question was transformed by Paul Erdős and Alfréd Rényi in a series of papers from 1959 onward11011. They introduced the random graph: fix $n$ vertices and include each possible edge independently with probability $p$. As $p$ rises, the random graph undergoes sharp transitions—most famously, when $p$ passes $1/n$, a giant connected component suddenly appears. This was a new kind of mathematics: instead of asking whether a particular graph has a property, one asks with what probability a random graph does, and finds that for many properties the answer flips abruptly at a threshold. Erdős and Rényi's work, together with Erdős's broader use of randomness as a proof technique, made probabilistic reasoning a permanent part of graph theory and seeded the modern study of random structures112.
Extremal questions: how large can a graph be?
A third current asked for the maximum number of edges a graph can have while avoiding some forbidden substructure113. The founding result is Turán's theorem (1941): a graph on $n$ vertices with no clique (a set of mutually adjacent vertices) of size $r+1$ has at most a certain number of edges, achieved by a complete multipartite graph1314. This launched extremal graph theory, which grew through the 1960s and 1970s with the work of Erdős, Vera T. Sós, and many others into a central branch, asking how local restrictions force global size. The same era saw the rise of structural results—theorems saying that a graph either contains a certain pattern or has a simple description—culminating much later in the graph minors programme of Neil Robertson and Paul Seymour (from the 1980s), which proved that graphs excluding a fixed minor have a tree-like decomposition, and in the 2000s in the graph limits theory of Lovász and others, which describes the large-scale behaviour of dense graphs by continuous objects called graphons.
Algebra, optimisation, and the computer
Algebra entered graph theory through the study of adjacency matrices—square arrays recording which vertices are joined—and their eigenvalues115. This algebraic graph theory connected spectral properties to structural ones: for instance, the eigenvalues of a graph's adjacency matrix encode information about its connectivity and its colouring. The field matured through the mid-twentieth century with work on strongly regular graphs, association schemes, and the interplay with group theory.
Meanwhile, practical demands produced combinatorial optimisation on graphs: finding shortest paths, minimum spanning trees, maximum matchings, and optimal flows through networks16171819. These problems, formalised in the 1930s–1950s, became the testing ground for algorithmic graph theory once computers arrived. The 1950s and 1960s brought foundational algorithms—Dijkstra's shortest-path method (1956), Kruskal's and Prim's spanning-tree algorithms, the Hungarian method for matching—and the realisation that some graph problems are computationally hard. The theory of NP-completeness (Cook, 1971; Karp, 1972) showed that problems such as finding a Hamiltonian cycle or colouring a graph with three colours are, in a precise sense, as hard as any problem in a large class, which reframed the field: exact answers might be out of reach, so approximation, special cases, and structural characterisations became central.
Networks and the present
The late twentieth century saw graph theory flow outward into the study of real networks120. Network science, emerging around the turn of the millennium, applied graph ideas to social, biological, and technological systems, identifying features such as the small-world property (short paths between most pairs) and scale-free degree distributions (a few highly connected hubs)202122. These empirical findings fed back into theory, raising new questions about robustness, spreading processes, and community structure.
Today the field is plural. Extremal and structural graph theory remain vigorous, with the graph minors theorem and the theory of graph limits as landmarks232425. Probabilistic methods and random graphs are central, and algorithmic graph theory drives both theory and practice110. Algebraic techniques connect graphs to representation theory and to quantum information. Open questions persist at every scale: the exact complexity of many natural problems, the fine structure of random graphs near their thresholds, the full reach of the graph limits programme, and the gap between what is provable and what is observed in real networks. The subject that began with seven bridges now underpins how we reason about connection itself.
References
- Graph theory (History, Topological graph theory, Graph enumeration, Extremal graph theory, Algebraic graph theory, Applications), Wikipedia
- Seven Bridges of Königsberg, Wikipedia
- Eulerian path, Wikipedia
- Graph coloring (History, introduction), Wikipedia
- Four color theorem, Wikipedia
- Planar graph, Wikipedia
- Chromatic polynomial (introduction, History), Wikipedia
- Bipartite graph, Wikipedia
- Graph enumeration, Wikipedia
- Random graph (History, introduction), Wikipedia
- Erdős–Rényi model, Wikipedia
- Probabilistic method, Wikipedia
- Extremal graph theory (introduction, History), Wikipedia
- Turán's theorem, Wikipedia
- Adjacency matrix, Wikipedia
- Combinatorial optimization, Wikipedia
- Network flow problem, Wikipedia
- Matching (graph theory), Wikipedia
- Shortest path problem, Wikipedia
- Network science, Wikipedia
- Small-world network, Wikipedia
- Scale-free network (introduction, History), Wikipedia
- Graph structure theorem, Wikipedia
- Graphon, Wikipedia
- Robertson–Seymour theorem, Wikipedia
The frameworks of Graph Theory
Each framework is a way of working the field has used: when it held, and the question it answers.
- 1736-Present
- 1852-Present
- 1857-Present
- 1930-Present
Algebraic graph theory
What do matrices and eigenvalues tell us about graphs?
About Algebraic graph theory
Algebraic Graph Theory emerged in the 1960s as a distinctive framework that answers a deceptively simple question: what can we learn about a graph by representing it with algebraic objects—matrices, polynomials, and groups? Instead of drawing pictures or counting edges directly, algebraic graph theorists translate graphs into the language of linear algebra and group theory, then use the powerful theorems of those fields to deduce structural properties. This approach proved especially fruitful for studying highly symmetric graphs, for understanding graph spectra, and for developing invariants that can distinguish non-isomorphic graphs. It is not a generic application of linear algebra to graphs; rather, it is a systematic program that treats the adjacency matrix, the Laplacian matrix, and the automorphism group as primary objects of study, each with its own deep theory.The core curriculum of a first course in algebraic graph theory typically follows a logical progression from matrices to spectra to symmetry. The foundational objects are the Adjacency Matrix and the Laplacian Matrix of a graph. From these matrices, one studies the Eigenvalues of Graphs, which form the basis of Spectral Graph Theory—a major subfield that relates graph properties (like connectivity, bipartiteness, and expansion) to the eigenvalues of its matrices. A central question is Graph Isomorphism: when are two graphs the same up to relabeling? Algebraic methods provide powerful invariants, including the spectrum and the Automorphism Group of a graph, which captures its symmetries. Cayley Graphs offer a rich class of examples built from groups, and they are often Regular Graphs, where every vertex has the same degree. More specialized but deeply studied families include Strongly Regular Graphs and Distance-Regular Graphs, which are defined by strong combinatorial regularity conditions that often yield elegant algebraic characterizations. Finally, the framework includes Graph Polynomials such as the Chromatic Polynomial (counting proper colorings) and the Matching Polynomial (counting matchings), as well as the Cycle Space and Cut Space of a graph, which are vector spaces over that encode the cycle and cut structure.The intellectual history of algebraic graph theory begins in the 1960s, when several mathematicians independently realized that linear algebra and group theory could be powerful tools for graph problems. The local dominance window for this framework is 1960 to 2026, and its key figures and seminal works belong squarely within that period. The earliest systematic treatments were Norman Biggs's 1974 book Algebraic Graph Theory and Chris Godsil and Gordon Royle's later 2001 of the same name, which together codified the curriculum. However, the framework's roots lie in earlier work: precursors include the use of matrices to study graphs by Gustav Kirchhoff (1847) in his work on electrical networks, and the development of group theory by Évariste Galois and others in the 19th century. The immediate predecessor framework, the Probabilistic Method (1959–present), offered a different, non-constructive approach to existence problems, while the contemporary Algorithmic Graph Theory (1960–present) focused on computational efficiency. Algebraic graph theory coexisted with these frameworks, often providing structural insights that complemented probabilistic existence proofs or algorithmic constructions. Key figures include Norman Biggs (who pioneered the study of distance-regular graphs and algebraic methods for strongly regular graphs), Chris Godsil (whose work on algebraic combinatorics and graph spectra is foundational), and László Lovász (whose 1979 book Combinatorial Problems and Exercises and his work on graph spectra and the theta function bridged algebraic and extremal graph theory). Seminal works include Biggs's 1974 Algebraic Graph Theory, Godsil and Royle's 2001 Algebraic Graph Theory, and the 1988 monograph Spectra of Graphs by Dragoš Cvetković, Michael Doob, and Horst Sachs, which established spectral graph theory as a central branch. The framework's legacy is a set of powerful invariants and techniques that remain essential in modern graph theory, particularly in spectral clustering, network science, and the study of expander graphs.The 15 concepts its tower teaches
- Adjacency Matrix
- Automorphism Group
- Cayley Graphs
- Chromatic Polynomial
- Cut Space
- Cycle Space
- Distance-Regular Graphs
- Eigenvalues of Graphs
- Graph Isomorphism
- Graph Polynomials
- Laplacian Matrix
- Matching Polynomial
- Regular Graphs
- Spectral Graph Theory
- Strongly Regular Graphs
- 1941-Present
Extremal graph theory
How many edges can a graph have without a given pattern?
- 1950-Present
Algorithmic and combinatorial optimisation on graphs
What is the best algorithm for a graph problem?
- 1959-Present
- 1980-Present
Structural graph theory and graph minors
What structure forces a graph to contain a pattern?
- 1998-Present
- 2000-Present
How the ideas connect
Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.
Extremal graph theory grew out of Eulerian foundations
Turán's 1941 extremal theorem asked how many edges a graph can have without a given subgraph, a question that presupposes the vertex-edge framework Euler had fixed. Turán's complete multipartite extremal graphs are described in Eulerian terms.
Carried by Paul Turán.
Algebraic graph theory influenced by Graph coloring
Birkhoff's 1912 chromatic polynomial showed that colouring counts can be studied algebraically. Spectra and algebraic invariants of graphs were then related to chromatic number and to strongly regular graphs, a link made by Delsarte and others in the mid-twentieth century.
Carried by George David Birkhoff; Philippe Delsarte.
Algorithmic and combinatorial optimisation on graphs influenced by Graph coloring
Karp's 1972 list of NP-complete problems included graph colouring (three-colourability), reframing the colouring problem as a computational hardness question. Algorithmic work then sought approximation and special cases for chromatic-number problems.
Carried by Richard Karp.
Graphon influenced by Graph enumeration
Lovász and Szegedy's 2006 graphon theory uses counting homomorphisms of finite graphs, a technique rooted in enumerative and algebraic enumeration. The graphon limit is built from dense-graph counting data.
Carried by László Lovász; Balázs Szegedy.
Graphon influenced by Extremal graph theory
Graph limit theory grew out of extremal graph theory, using the densities of subgraphs in large graphs as the coordinates of a limiting object. Lovász and Szegedy's graphons formulate extremal questions as continuous variational problems.
Carried by László Lovász; Balázs Szegedy.
Network science influenced by Random graph
Network science took over random-graph models as its null model and adapted them: Watts and Strogatz's small-world model (1998) and Barabási and Albert's scale-free model (1999) modified Erdős-Rényi random graphs to match empirical data.
Carried by Duncan Watts; Steven Strogatz; Albert-László Barabási.
Graphon influenced by Random graph
The theory of graph limits was motivated in part by the dense random-graph models of Erdős and Rényi, whose convergent sequences of dense graphs have graphon limits. Lovász and Szegedy explicitly connected their work to quasi-randomness and random-graph theory.
Carried by László Lovász; Balázs Szegedy.
Graph coloring grew out of Eulerian foundations
Guthrie's four-colour conjecture was posed in 1852, after Euler's foundational framing of vertices and edges. The colouring problem presupposed that concrete maps could be abstracted to graphs, the move Euler had established.
Carried by Francis Guthrie; Arthur Cayley.
Algebraic graph theory grew out of Eulerian foundations
Matrix and eigenvalue methods were applied to adjacency matrices of graphs, which are defined by Euler's points-and-lines abstraction. The algebra works on graph structures traced to the founding framework.
Structural graph theory and graph minors influenced by Graph coloring
Structural graph theory grew out of questions about colouring and planarity, including the four-colour problem and Hadwiger's conjecture relating chromatic number to minors. Robertson and Seymour's minor programme addressed such structural questions directly.
Carried by Neil Robertson; Paul Seymour.
Beyond the field
Where Graph Theory's ideas came from in other fields, and what they led to there: the strongest 12 of 67 links.
Graph coloring grew out of Graph Theory in Combinatorics
Graph colouring arose as a problem posed within graph theory: the four-colour question about maps was framed in terms of colouring the regions of a planar graph, and became a central strand of the field.
Carried by Francis Guthrie; Augustus De Morgan.
Graph enumeration grew out of Graph Theory in Combinatorics
Graph enumeration is a subfield of graph theory, counting the objects (graphs, trees, maps) that the parent field defines; it developed as graph theory turned to systematic counting.
Carried by Arthur Cayley.
Algebraic graph theory grew out of Graph Theory in Combinatorics
Algebraic graph theory is a branch of graph theory, taking the objects of the parent field and studying them with algebraic machinery.
Algebraic graph theory led to Spectral graph theory in Graph Algorithms
Spectral graph theory grew out of algebraic graph theory, using adjacency and Laplacian matrices and their eigenvalues to study graph structure. The matrix-based algebraic tradition supplied the objects the spectral programme analyses.
Extremal graph theory led to Regularity Method in Extremal Combinatorics
The regularity method was developed within extremal graph theory as a tool for proving density theorems, most famously Szemeredi's theorem and the Erdos-Stone-Simonovits results. It is a branch of extremal graph theory's programme of determining extremal densities.
Carried by Endre Szemerédi.
Extremal graph theory grew out of Graph Theory in Combinatorics
Extremal graph theory is a subfield of graph theory, posing extremal questions about the objects the parent field defines.
Carried by Paul Erdős.
Algorithmic and combinatorial optimisation on graphs grew out of Graph Theory in Combinatorics
Algorithmic and combinatorial optimisation on graphs is a branch of graph theory, taking graph structures as its domain and developing algorithms for problems defined on them.
Algorithmic and combinatorial optimisation on graphs led to Network Flow and Cut Theory in Graph Algorithms
Network flow and cut theory is a branch of algorithmic graph optimization: Ford and Fulkerson's max-flow min-cut work built directly on the graph-theoretic optimization tradition.
Carried by Lester Ford; Delbert Fulkerson.
Random graph led to Sharp Threshold Theory in Probabilistic Combinatorics
Sharp threshold theory was developed to explain and generalise the threshold phenomena first observed in Erdős–Rényi random graphs, such as the emergence of connectivity and giant components.
Carried by Ehud Friedgut; Jean Bourgain.
Random graph grew out of Probabilistic Method in Combinatorics
Erdős's probabilistic method, developed from the 1940s, supplied the existence arguments that Erdős and Rényi used to found the theory of random graphs in 1959–1960. The random graph is a direct application and outgrowth of that method.
Carried by Paul Erdős; Alfréd Rényi; On Random Graphs (1959).
Random graph grew out of Probabilistic Method in Probabilistic Combinatorics
The probabilistic method as practised in probabilistic combinatorics is the direct source of the random graph model: Erdős and Rényi's 1959–1960 papers applied exactly these counting and expectation arguments to random graphs.
Carried by Paul Erdős; Alfréd Rényi.
Random graph influenced Graphon in Probabilistic Combinatorics
The theory of graph limits grew out of the study of convergent sequences of dense random graphs and of quasirandom graphs; the counting lemmas and cut metric used to define graphons come directly from this random-graph work.
Carried by László Lovász; Balázs Szegedy; Christian Borgs.

Graph Theory is a planet in Nousfarer
Its city has a tower for each of these 10 frameworks. Land, walk in, and climb one concept at a time.
Land on Graph TheoryRelated fields
Fields its ideas are linked to
- Combinatorics 11 links
- Graph Algorithms 9 links
- Extremal Combinatorics 9 links
- Networks 6 links
- Algorithms 4 links
- Enumerative Combinatorics 4 links
- Probabilistic Combinatorics 4 links
- Abstract Algebra 2 links
- Matroid Theory 2 links
- Distributed Algorithms 1 link
- Systems Biology 1 link
- Algebraic Combinatorics 1 link