Loading field map
Graph theory is the branch of discrete mathematics that studies graphs: mathematical structures used to model pairwise relations between objects. A graph consists of a set of vertices (also called nodes or points) and a set of edges (also called links or lines), where each edge connects a pair of vertices. Despite this deceptively simple definition, graph theory has grown into a rich and sprawling field with deep internal structure, profound connections to other areas of mathematics, and applications ranging from computer networking to molecular chemistry.
The core of graph theory lies in the tension between the simplicity of its basic objects and the complexity of the questions one can ask about them. A graph can be undirected, where each edge is a symmetric connection between two vertices, or directed (a digraph), where each edge has a direction from one vertex to another. Edges may also carry weights, representing costs, distances, capacities, or other quantitative attributes. These variations are not mere technicalities; they fundamentally change the nature of the problems that arise.
The central questions of graph theory fall into several enduring families. Connectivity asks whether there is a path between two vertices, how many disjoint paths exist, and how robust the network is to the removal of vertices or edges. Coloring problems ask how to assign labels (colors) to vertices or edges subject to constraints—most famously, ensuring that adjacent vertices receive different colors. Extremal graph theory asks how large a graph can be before it must contain a particular substructure. Matching theory concerns selecting edges so that no two share a vertex, with applications to assignment problems. Planarity asks whether a graph can be drawn in the plane without edge crossings. Hamiltonicity asks whether a graph contains a cycle that visits every vertex exactly once.
What unites these questions is a focus on structural properties that are invariant under relabeling of vertices. Graph theory is fundamentally about the shape of relations, not the identity of the objects being related. This abstraction is the source of both its power and its difficulty: a single graph-theoretic result can apply to road networks, social connections, electrical circuits, and molecular structures simultaneously, but the same abstraction strips away the numerical and geometric tools that make problems in other areas more tractable.
The origins of graph theory are usually traced to Leonhard Euler's 1736 solution of the Königsberg bridge problem. The citizens of Königsberg (now Kaliningrad) had wondered whether one could walk through the city crossing each of its seven bridges exactly once and return to the starting point. Euler recognized that the precise layout of the city's landmasses and bridges could be abstracted into a structure of vertices (landmasses) and edges (bridges), and he proved that such a walk is impossible because four of the vertices have odd degree (an odd number of incident edges). This result is often cited as the birth of graph theory, though Euler himself did not use the term "graph" and did not develop a general theory from this example.
For more than a century afterward, graph-theoretic ideas appeared sporadically in the work of various mathematicians. Gustav Kirchhoff used graph-theoretic reasoning in the 1840s to analyze electrical networks, developing what would later be recognized as spanning tree theory. Arthur Cayley and James Joseph Sylvester used diagrams of chemical structures in the 1850s to enumerate isomers of organic compounds, effectively working with trees (connected acyclic graphs). William Rowan Hamilton's "Icosian game" of 1857 asked players to find a cycle visiting all vertices of a dodecahedron, giving rise to the concept of Hamiltonian cycles. These were isolated investigations, not yet a unified field.
The emergence of graph theory as a coherent discipline is often associated with the four color problem, posed by Francis Guthrie in 1852 and publicized by Augustus De Morgan. The question—whether four colors always suffice to color any map so that adjacent regions receive different colors—was deceptively simple and resisted solution for over a century. It was not until 1976 that Kenneth Appel and Wolfgang Haken announced a proof, which relied on extensive computer assistance to check thousands of cases. This proof was controversial at the time because it was the first major theorem to depend essentially on computation, and it remains a landmark in the history of both graph theory and mathematical proof.
The late nineteenth and early twentieth centuries saw the first systematic treatments of graph theory. Dénes Kőnig wrote the first textbook on the subject in 1936, consolidating the field's results and establishing its terminology. The mid-twentieth century brought a surge of activity driven by the rise of computer science and operations research. The need to model communication networks, scheduling problems, and transportation systems gave graph theory both new problems and new motivation. The development of algorithms for finding shortest paths, maximum flows, and minimum spanning trees turned graph theory into a computational discipline as much as a pure mathematical one.
Graph theory is not organized around a small number of rival schools in the way that, say, twentieth-century physics was divided between competing interpretations of quantum mechanics. Instead, the field is characterized by a set of distinct but overlapping research traditions, each with its own questions, methods, and standards of proof. These traditions coexist and cross-fertilize, and many researchers work in several of them.
One major tradition asks how global parameters of a graph—such as the number of edges or the minimum degree—force the existence of local substructures. The foundational result here is Turán's theorem (1941), which determines the maximum number of edges a graph can have without containing a complete subgraph on a given number of vertices. This line of inquiry was transformed by the work of Paul Erdős and Alfréd Rényi in the late 1950s, who introduced the random graph model in which each possible edge is included independently with a fixed probability. The probabilistic method, pioneered by Erdős, uses random graphs to prove the existence of graphs with desired properties: if a randomly chosen graph has a property with positive probability, then some graph must have it.
This tradition has produced some of the most striking results in modern graph theory, including the Erdős–Stone theorem, which gives a remarkably precise asymptotic description of extremal behavior, and the development of graph limits and regularity lemmas, which allow one to approximate large graphs by simpler structures. The probabilistic method has become a standard tool not just in extremal graph theory but throughout discrete mathematics. The tradition is characterized by an emphasis on asymptotic questions—what happens as the number of vertices grows large—and by a willingness to accept nonconstructive proofs that show existence without exhibiting the object in question.
A second tradition seeks to understand the internal architecture of graphs: how they can be decomposed into simpler pieces, what obstructions prevent them from having certain properties, and how their global structure constrains their local behavior. This tradition is exemplified by the theory of graph minors developed by Neil Robertson and Paul Seymour in a series of papers beginning in the 1980s. Their work established that graphs can be ordered by a relation of "minor" (roughly, obtained by deleting vertices or edges and contracting edges), and that this ordering is well-quasi-ordered: any infinite set of graphs contains two where one is a minor of the other. This deep result implies that any property closed under taking minors can be characterized by a finite set of forbidden minors, and it leads to efficient algorithms for many graph problems.
The structural tradition also includes the theory of perfect graphs, developed by Claude Berge and others, which studies graphs where the chromatic number equals the size of the largest clique in every induced subgraph. The proof of the strong perfect graph theorem by Maria Chudnovsky, Robertson, Seymour, and Robin Thomas in 2002 characterized all such graphs in terms of forbidden induced subgraphs, a result that had been conjectured by Berge in 1961. This tradition values explicit structural descriptions: rather than merely proving that something exists, it aims to say exactly what it looks like.
A third tradition treats graphs primarily as computational objects. Here the central questions concern the design of efficient algorithms for graph problems and the classification of which problems can be solved efficiently at all. This tradition emerged in the 1960s and 1970s with the development of the theory of NP-completeness by Stephen Cook, Richard Karp, and others. Many natural graph problems—including Hamiltonian cycle, graph coloring, and finding a maximum independent set—turned out to be NP-complete, meaning that no efficient algorithm is known for them and that finding one would solve a vast class of open problems.
The algorithmic tradition has developed a rich toolkit for dealing with this hardness. Parameterized complexity studies problems with respect to a secondary parameter (such as the size of the solution sought), asking whether a problem can be solved in time that is polynomial in the graph size but possibly exponential in the parameter. Fixed-parameter tractable algorithms have been developed for many problems that are NP-complete in general. The theory of treewidth and related graph width parameters, developed by Robertson and Seymour in the context of their minor theory, has proven especially fruitful: many hard problems become tractable on graphs of bounded treewidth, and many real-world networks have small treewidth in practice. Approximation algorithms provide another response to hardness, seeking solutions that are provably close to optimal.
This tradition is distinguished by its standards of proof: results must come with explicit algorithms and rigorous complexity bounds. It has deep connections to the structural tradition, since structural decompositions often yield algorithms, but it is also driven by practical concerns and by the internal logic of computational complexity theory.
A fourth tradition brings tools from linear algebra to bear on graphs. The adjacency matrix of a graph records which vertices are adjacent, and the Laplacian matrix records degree information. The eigenvalues and eigenvectors of these matrices encode substantial information about the graph's structure. The spectral gap—the difference between the largest and second-largest eigenvalues of the Laplacian—controls how quickly random walks on the graph mix and how well the graph expands. Expander graphs, which are sparse but highly connected, have proven important in computer science, from error-correcting codes to pseudorandomness.
This tradition also includes algebraic graph theory in a broader sense, using group theory and representation theory to study graphs with high symmetry. The theory of strongly regular graphs and the classification of distance-transitive graphs draw on deep algebraic machinery. The algebraic approach often provides different proofs of results obtained combinatorially and sometimes yields results that seem inaccessible to purely combinatorial methods. Its limitation is that spectral methods typically give information about averages and global properties, not about the precise location of substructures.
These traditions are not isolated silos. The most influential work in modern graph theory often combines them. The probabilistic method is used to construct graphs that are then analyzed structurally. Spectral methods provide bounds that are used in extremal arguments. Algorithmic results depend on structural decompositions, and structural results are often motivated by algorithmic questions. The proof of the four color theorem, for instance, combined structural reduction arguments with extensive computation. The theory of graph minors is simultaneously a structural theory, an algorithmic theory, and a source of extremal results.
One notable synthesis is the regularity lemma of Endre Szemerédi, which originated in extremal graph theory but has become a general tool. It states that every sufficiently large graph can be partitioned into a bounded number of parts such that the edges between most pairs of parts behave pseudorandomly. This lemma, originally a technical tool for proving a result in number theory, has found applications throughout graph theory and beyond, illustrating how techniques migrate between traditions.
Current graph theory is characterized by several active frontiers. The semidefinite programming approach to graph problems, initiated by László Lovász, has created new connections between graph theory and optimization. The study of graph limits and exchangeable random graphs has brought graph theory into contact with probability theory and analysis in new ways. The development of property testing in computer science asks how one can determine whether a graph has a property by examining only a small sample of its edges, a question that connects extremal graph theory with computational complexity.
The field has also expanded into new application domains. Network science uses graph-theoretic tools to study social networks, biological networks, and the internet, though it often emphasizes statistical properties of large real-world networks rather than the worst-case guarantees that dominate classical graph theory. Spectral graph theory has found applications in machine learning, where graph Laplacians are used for clustering and dimensionality reduction. The theory of graph neural networks in artificial intelligence attempts to learn functions on graphs, raising new questions about the expressive power of graph-based computations.
Throughout these developments, the core of graph theory remains what it has always been: the study of how simple combinatorial relations between objects give rise to complex and often surprising global structure. The field's power lies in its abstraction, which allows a single mathematical framework to illuminate problems across mathematics, computer science, and the natural and social sciences. Its difficulty lies in the same abstraction, which strips away the tools that make other areas of mathematics tractable and forces researchers to develop new methods suited to the purely relational nature of their objects.