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

still a working view ended · each leads to its entry below

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

  1. Graph theory (History, Topological graph theory, Graph enumeration, Extremal graph theory, Algebraic graph theory, Applications), Wikipedia
  2. Seven Bridges of Königsberg, Wikipedia
  3. Eulerian path, Wikipedia
  4. Graph coloring (History, introduction), Wikipedia
  5. Four color theorem, Wikipedia
  6. Planar graph, Wikipedia
  7. Chromatic polynomial (introduction, History), Wikipedia
  8. Bipartite graph, Wikipedia
  9. Graph enumeration, Wikipedia
  10. Random graph (History, introduction), Wikipedia
  11. Erdős–Rényi model, Wikipedia
  12. Probabilistic method, Wikipedia
  13. Extremal graph theory (introduction, History), Wikipedia
  14. Turán's theorem, Wikipedia
  15. Adjacency matrix, Wikipedia
  16. Combinatorial optimization, Wikipedia
  17. Network flow problem, Wikipedia
  18. Matching (graph theory), Wikipedia
  19. Shortest path problem, Wikipedia
  20. Network science, Wikipedia
  21. Small-world network, Wikipedia
  22. Scale-free network (introduction, History), Wikipedia
  23. Graph structure theorem, Wikipedia
  24. Graphon, Wikipedia
  25. 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.

  1. 1736-Present

    Eulerian foundations

    When does a walk traverse every edge exactly once?

    Fly to its tower in Nousfarer

  2. 1852-Present

    Graph coloring

    How few labels can colour a graph's vertices?

    Fly to its tower in Nousfarer

  3. 1857-Present

    Graph enumeration

    How many graphs of a given kind are there?

    Fly to its tower in Nousfarer

  4. 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 F2\mathbb{F}_2 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 \text{} 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

    Fly to its tower in Nousfarer

  5. 1941-Present

    Extremal graph theory

    How many edges can a graph have without a given pattern?

    Fly to its tower in Nousfarer

  6. 1950-Present
  7. 1959-Present
  8. 1980-Present

    Structural graph theory and graph minors

    What structure forces a graph to contain a pattern?

    Fly to its tower in Nousfarer

  9. 1998-Present

    Network science

    What patterns do real networks share?

    Fly to its tower in Nousfarer

  10. 2000-Present

    Graphon

    What continuous object limits a sequence of dense graphs?

    Fly to its tower in Nousfarer

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.

Eulerian foundationsGraph coloringGraph enumerationAlgebraic graph theoryExtremal graph theoryAlgorithmic and combinatorial optimis…Random graphStructural graph theory and graph min…Network scienceGraphon

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.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

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 Theory

Related fields

Fields its ideas are linked to

More in Combinatorics

See where Graph Theory sits on the Map of Human Knowledge