Loading field map
Graph theory is the branch of combinatorics 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 one of the most active and broadly applicable areas of modern mathematics, with deep connections to computer science, physics, biology, and the social sciences.
The basic definition of a graph admits many variations, and choosing the right variant is often the first step in any graph-theoretic investigation. In a simple graph, each edge connects two distinct vertices, and there is at most one edge between any pair. A multigraph allows multiple edges between the same pair of vertices, while a loop is an edge connecting a vertex to itself. Directed graphs (or digraphs) give each edge an orientation, so that an edge goes from one vertex to another; these are essential for modeling asymmetric relationships such as influence, information flow, or predation.
Beyond these basic choices, graphs can be weighted (each edge carries a numerical value), colored (vertices or edges are assigned labels), or infinite (with infinitely many vertices). The field also studies hypergraphs, where edges can connect more than two vertices, and matroids, which abstract the notion of independence in graphs and other combinatorial structures. Each generalization extends the expressive power of the model, but also complicates the questions one can ask.
Graph theory is organized less around a single unifying problem than around a cluster of recurring questions that appear in many guises. One fundamental theme is connectivity: when can one travel from a given vertex to another along edges, and how many edges or vertices must be removed to disconnect a graph? This question underlies everything from network reliability to the design of communication systems.
A second major theme is coloring and partitioning. The chromatic number of a graph is the minimum number of colors needed to assign to vertices so that adjacent vertices receive different colors. The famous four-color theorem—stating that every planar map can be colored with four colors—was the first major theorem proved with substantial computer assistance, and it remains a landmark in the field. Related questions ask how to partition a graph into cliques, independent sets, or other structured subgraphs.
A third theme concerns paths and cycles. When does a graph contain a path that visits every vertex exactly once (a Hamiltonian path) or every edge exactly once (an Eulerian trail)? These questions, which date to the earliest days of the subject, have deep connections to optimization and to the theory of computational complexity. The traveling salesman problem—finding the shortest tour visiting all vertices of a weighted graph—is perhaps the most famous optimization problem in all of mathematics, and it is NP-hard, meaning that no efficient algorithm is known for solving it in general.
A fourth theme is structure and decomposition. Many graphs can be understood by breaking them into simpler pieces: trees, complete graphs, cycles, or more complex building blocks. The theory of graph minors, developed by Neil Robertson and Paul Seymour, provides a powerful framework for understanding when one graph can be obtained from another by contracting edges and deleting vertices. This theory has produced deep structural results, including the graph minor theorem, which states that every family of graphs closed under taking minors can be characterized by a finite set of forbidden minors.
The origins of graph theory are usually traced to Leonhard Euler's 1736 solution of the Königsberg bridge problem. The city of Königsberg had seven bridges connecting four land masses, and Euler showed that it was impossible to walk across each bridge exactly once and return to the starting point. In doing so, he introduced the abstract idea of representing land masses as vertices and bridges as edges, and he characterized exactly when such a walk exists: a connected graph has an Eulerian circuit if and only if every vertex has even degree. This result is often cited as the birth of both graph theory and topology.
For more than a century after Euler, graph-theoretic ideas appeared sporadically in the work of mathematicians studying electrical circuits, chemical structures, and recreational puzzles. The term "graph" itself was introduced by J. J. Sylvester in 1878, drawing an analogy with chemical diagrams. In the late nineteenth century, the subject began to consolidate as a distinct field. Arthur Cayley's work on counting trees, motivated by questions in chemistry, established enumeration as a central technique. The four-color conjecture, posed in 1852, stimulated a century of research and led to the development of important tools such as the theory of planar graphs and the concept of graph coloring.
The twentieth century saw graph theory transform from a collection of isolated results into a mature mathematical discipline. The Hungarian school, led by Dénes Kőnig, produced the first textbook on the subject in 1936 and established many of its foundational results. The development of linear programming and combinatorial optimization in the 1940s and 1950s brought graph theory into close contact with operations research and economics. The rise of computer science in the 1960s and 1970s created a vast new source of problems and applications, from the analysis of algorithms to the design of integrated circuits. The proof of the four-color theorem in 1976, which relied on extensive computer checking, sparked a lasting debate about the nature of mathematical proof and the role of computation in mathematics.
Graph theory is not divided into sharply separated schools, but several distinct approaches have shaped the field, each with its own questions, methods, and standards of explanation.
Extremal graph theory asks how large a graph can be before it must contain a given substructure. The classic result in this area is Turán's theorem, which determines the maximum number of edges in a graph that does not contain a complete subgraph on a given number of vertices. This line of inquiry was dramatically extended by Paul Erdős and his collaborators, who introduced probabilistic methods in the 1940s. The probabilistic method proves the existence of a graph with certain properties by showing that a randomly chosen graph has a positive probability of having those properties. This approach has produced remarkably sharp results about the thresholds at which random graphs acquire various properties, and it has become a standard tool not only in graph theory but throughout combinatorics.
The probabilistic method also gave rise to the study of random graphs themselves, initiated by Erdős and Alfréd Rényi. A random graph on a large number of vertices, where each edge appears independently with some probability, exhibits striking phase transitions: as the edge probability crosses a critical threshold, the graph suddenly develops a giant connected component, then becomes connected, then acquires Hamiltonian cycles. These phenomena have found applications in epidemiology, social network analysis, and the study of the internet.
A second major approach emphasizes the classification and decomposition of graphs according to their structure. This tradition, associated with the work of Robertson and Seymour on graph minors, seeks to understand when a graph can be embedded in a surface, decomposed into simpler pieces, or characterized by forbidden substructures. The theory of treewidth, which measures how close a graph is to being a tree, is a central concept in this tradition. Many hard computational problems become tractable on graphs of bounded treewidth, making this notion essential for both theoretical and practical algorithm design.
This structural tradition has deep connections to topological graph theory, which studies graphs drawn on surfaces. The question of which graphs can be drawn on the plane without edge crossings (planar graphs) was settled by Kuratowski's theorem, which characterizes planar graphs by two forbidden subgraphs. The generalization of this question to other surfaces leads to the theory of graph embeddings and to the concept of the genus of a graph.
A third approach brings the tools of linear algebra to bear on graphs. The adjacency matrix of a graph records which vertices are connected, and its eigenvalues and eigenvectors encode important information about the graph's structure. The field of spectral graph theory, developed extensively by the Hungarian-American mathematician László Lovász and others, uses these algebraic invariants to study connectivity, expansion, and the number of spanning trees. The Laplacian matrix, a close relative of the adjacency matrix, plays a central role in this theory and has found applications in machine learning, image processing, and the analysis of electrical networks.
Spectral methods are particularly powerful for studying expander graphs, which are sparse graphs that are nevertheless highly connected. Expanders have remarkable properties: they are simultaneously sparse and well-connected, making them useful in the design of error-correcting codes, pseudorandom generators, and communication networks. The construction of expanders, originally achieved through probabilistic arguments, was later made explicit through connections with group theory and number theory.
A fourth approach treats graphs primarily as the setting for optimization problems. This tradition, which grew out of the work of George Dantzig, Jack Edmonds, and others in the mid-twentieth century, seeks efficient algorithms for finding optimal structures in graphs: shortest paths, minimum spanning trees, maximum matchings, and minimum cuts. The theory of polynomial-time algorithms and the distinction between tractable and intractable problems (the P versus NP question) emerged from this work and has become a central concern of theoretical computer science.
The optimization tradition has produced some of the most beautiful results in graph theory. The max-flow min-cut theorem, proved by Ford and Fulkerson, states that the maximum amount of flow that can be sent through a network equals the minimum capacity of a cut separating the source from the sink. This theorem has found applications in fields as diverse as transportation planning, image segmentation, and the study of electrical networks. The theory of matching, developed by Tutte, Edmonds, and others, provides efficient algorithms for finding maximum matchings in graphs and has deep connections to the theory of matroids.
Modern graph theory is characterized by the productive interaction of these traditions. Extremal and probabilistic methods are used to understand the typical behavior of large graphs, while structural results provide the framework for algorithmic design. Spectral methods offer powerful tools for analyzing the global properties of graphs, and optimization techniques provide the computational backbone for applications.
One of the most active contemporary areas is the study of large-scale networks. The internet, social networks, biological networks, and transportation systems all give rise to graphs with millions or billions of vertices. These networks exhibit striking regularities—such as the "small-world" phenomenon, in which any two vertices are connected by a short path, and "scale-free" degree distributions, in which a few vertices have very high degree while most have low degree—that are not captured by classical random graph models. The development of more realistic network models, and the analysis of processes such as information diffusion and epidemic spreading on these networks, is a vibrant interdisciplinary field that draws on graph theory, probability, and statistical physics.
Another frontier is the study of graph limits and graphons. Just as a sequence of numbers can converge to a limit, a sequence of large graphs can converge to a limiting object called a graphon, which is a symmetric measurable function on the unit square. This theory, developed by Lovász and Balázs Szegedy, provides a framework for understanding the asymptotic behavior of large graphs and has connections to extremal graph theory, statistical physics, and the theory of exchangeable random graphs.
The interaction between graph theory and computer science continues to deepen. The theory of property testing asks how many queries are needed to determine whether a large graph has a given property or is far from having it. The theory of parameterized complexity studies which problems become tractable when a parameter of the input is held fixed. And the theory of graph neural networks, which has emerged from machine learning, uses graph-structured data to learn patterns and make predictions, creating new mathematical questions about the expressive power of these models.
Graph theory also maintains deep connections with other branches of mathematics. The chromatic polynomial of a graph, which counts the number of ways to color it with a given number of colors, is a central object in algebraic combinatorics. The Tutte polynomial, which generalizes the chromatic polynomial and the flow polynomial, encodes a remarkable amount of information about a graph and has connections to knot theory, statistical mechanics, and matroid theory. The theory of graph homomorphisms connects graph theory to universal algebra and to the study of constraint satisfaction problems.
What makes graph theory a single field, despite the diversity of its methods and applications, is the centrality of the graph as an object of study. A graph is at once a purely combinatorial object, a geometric object that can be drawn and embedded, an algebraic object with matrices and polynomials, and a computational object with algorithms and complexity. The same graph can be studied from all of these perspectives, and insights from one perspective often illuminate the others.
This unity is also reflected in the way graph theorists work. A typical research paper in the field might combine probabilistic arguments with algebraic techniques, or use structural decomposition to design an algorithm, or draw on optimization theory to prove a purely combinatorial result. The field rewards versatility and cross-fertilization, and its practitioners move freely between the different traditions.
For the educated newcomer, the most useful way to approach graph theory is to learn the basic vocabulary—vertices, edges, paths, cycles, connectivity, coloring—and then to explore the different questions that can be asked about these objects. The field is large enough that no one can master all of it, but its central ideas are accessible and its applications are everywhere. Whether one is interested in the mathematics of networks, the design of algorithms, or the beauty of combinatorial structure, graph theory offers a rich and rewarding landscape.