Graph Theory Guide: Networks, Trees, and Graph Algorithms
Introduction
Graph theory is the study of networks — collections of points connected by lines. A graph consists of vertices (the points) and edges (the connections), and this simple structure can model an astonishing range of phenomena. Social networks, transportation systems, chemical molecules, computer networks, electrical circuits, and the internet itself are all graphs at their core.
The field began with Euler’s solution of the Königsberg bridge problem in 1736. The city of Königsberg had seven bridges connecting two islands to the mainland, and the question was whether a person could walk through the city crossing each bridge exactly once. Euler proved it impossible, and in doing so founded graph theory. His insight was to abstract away everything except the pattern of connections — the essence of the network.
Basic Concepts
A graph G = (V, E) consists of a set V of vertices and a set E of edges, where each edge connects a pair of vertices. Graphs can be directed (edges have direction) or undirected (edges are symmetric). They can be simple (at most one edge between any pair) or contain multiple edges and loops.
Degree and Regularity
The degree of a vertex is the number of edges incident to it. The handshaking lemma states that the sum of all vertex degrees equals twice the number of edges — every edge contributes to two degrees. This seemingly trivial observation has powerful consequences. In any graph, the number of vertices of odd degree is even.
A regular graph has all vertices of the same degree. Complete graphs Kₙ have edges between every pair of vertices, making every vertex of degree n-1. Bipartite graphs have vertices partitioned into two sets, with edges only between the sets. Complete bipartite graphs K_{m,n} have all possible edges between the partitions.
Trees
A tree is a connected graph with no cycles. Trees are the minimal connected graphs — removing any edge disconnects them. They satisfy the fundamental relation |E| = |V| - 1, and any connected graph satisfying this relation is a tree.
Spanning Trees
A spanning tree of a graph is a subgraph that is a tree and includes all vertices. Every connected graph has at least one spanning tree. Cayley’s formula states that the complete graph Kₙ has n^(n-2) spanning trees, a result that connects graph theory to combinatorics.
Minimum spanning trees find applications in network design. Kruskal’s algorithm and Prim’s algorithm efficiently find a spanning tree of minimum total weight. These algorithms are fundamental in computer science and operations research.
Planar Graphs
A planar graph can be drawn in the plane without edge crossings. Euler’s formula V - E + F = 2 relates the numbers of vertices, edges, and faces of a connected planar graph. This formula has many consequences.
Kuratowski’s Theorem
Kuratowski’s theorem characterizes planar graphs: a graph is planar if and only if it does not contain a subdivision of K₅ (the complete graph on five vertices) or K_{3,3} (the complete bipartite graph with three vertices on each side). These two graphs are the basic building blocks of nonplanarity.
The four-color theorem states that every planar graph can be colored with at most four colors so that adjacent vertices have different colors. Proved in 1976 by Appel and Haken, it was the first major theorem proved using a computer. The proof reduced the problem to checking 1,936 cases, a task that could only be done computationally. This result connects graph theory to set theory through the foundations of mathematical proof.
Graph Coloring
Graph coloring assigns colors to vertices such that adjacent vertices have different colors. The chromatic number χ(G) is the minimum number of colors needed. Determining the chromatic number of a general graph is an NP-hard problem.
Brooks’ Theorem
Brooks’ theorem bounds the chromatic number in terms of maximum degree: for a connected graph G that is not a complete graph or an odd cycle, χ(G) ≤ Δ(G), where Δ(G) is the maximum degree. This theorem gives a simple but useful upper bound.
Map coloring is the original motivation for graph coloring. The dual graph of a map has vertices for regions and edges between adjacent regions. Coloring the dual graph is equivalent to coloring the map with the condition that adjacent regions have different colors.
Network Flows
A flow network is a directed graph with a source, a sink, and capacities on edges. The maximum flow problem asks how much flow can be sent from source to sink without exceeding capacities. The Ford-Fulkerson algorithm solves this problem.
Max Flow Min Cut Theorem
The max flow min cut theorem states that the maximum flow equals the minimum capacity of a cut separating the source from the sink. This theorem is fundamental in combinatorial optimization and has applications in transportation, telecommunications, and logistics.
The connection between flows and cuts extends to many areas. Matching problems in bipartite graphs reduce to flow problems. The assignment problem — matching workers to jobs optimally — is solved by flow algorithms. These applications connect graph theory to abstract algebra and operations research.
Spectral Graph Theory
Spectral graph theory studies graphs through the eigenvalues of their associated matrices. The adjacency matrix of a graph has entries Aᵢⱼ = 1 if vertices i and j are adjacent and 0 otherwise. The Laplacian matrix L = D - A encodes degree information along with adjacency.
The eigenvalues of these matrices reveal structural properties of graphs. The second smallest eigenvalue of the Laplacian, called the algebraic connectivity, measures how well-connected the graph is. The largest eigenvalue of the adjacency matrix relates to the maximum degree and the number of edges.
Applications of Spectral Methods
Spectral clustering uses the eigenvectors of the Laplacian to partition graphs into clusters. The Cheeger inequality relates the spectral gap — the difference between the first two eigenvalues — to the edge expansion of the graph. Expander graphs, which are sparse but highly connected, have applications in network design and error-correcting codes.
Spectral graph theory connects graph theory to linear algebra and functional analysis. The study of random walks on graphs uses spectral methods to analyze mixing times and hitting probabilities.
Ramsey Theory
Ramsey theory asks: how large must a graph be before it necessarily contains a given substructure? Ramsey’s theorem states that for any integers r and s, there exists an R(r, s) such that any graph with at least R(r, s) vertices contains either a complete subgraph of size r or an independent set of size s.
The exact values of Ramsey numbers are notoriously difficult to compute. R(3, 3) = 6, R(4, 4) = 18, but R(5, 5) is unknown — only bounds are known, and they lie between 43 and 48. Erdős famously said that if aliens demanded the value of R(5, 5) or face destruction, humanity could compute it within a year; if they demanded R(6, 6), humanity would be destroyed.
Algebraic Graph Theory
Algebraic graph theory uses group theory and linear algebra to study graphs. The automorphism group of a graph consists of permutations of vertices that preserve adjacency. Cayley graphs provide a visual representation of groups: the vertices are group elements, and edges connect elements that differ by multiplication by a generator.
The spectrum of a graph — the eigenvalues of its adjacency matrix — encodes structural information. Strongly regular graphs have precisely three eigenvalues and correspond to symmetric designs. Distance-regular graphs generalize strongly regular graphs and are related to association schemes.
Graph Minors
The graph minor theorem of Robertson and Seymour states that graphs are well-quasi-ordered by the minor relation: in any infinite collection of graphs, one is a minor of another. This theorem, proved in a monumental series of papers spanning twenty years, has deep consequences for graph structure theory.
A graph H is a minor of G if H can be obtained from G by deleting vertices, deleting edges, and contracting edges. The theory of graph minors leads to the structure theorem for graphs excluding a fixed minor, which describes such graphs as built from smaller pieces glued together in a tree-like way.
What is the difference between a path and a cycle? A path is a sequence of distinct vertices where consecutive vertices are adjacent. A cycle is a closed path where the first and last vertices are also adjacent.
Why are trees important? Trees are the simplest connected graphs. They appear naturally in hierarchies, data structures, phylogenetic trees, and spanning networks.
Is the four-color theorem accepted? Yes, the proof has been independently verified multiple times, both by computer and by the formalization of the proof in the Coq proof assistant.
How is graph theory used in computer science? Graph theory underlies data structures (trees, heaps), algorithms (shortest paths, network flows), and the structure of the internet and the web.
Combinatorics Guide — Abstract Algebra Guide — Set Theory Guide