Graph theory
In mathematics, graph theory is the study of structures formed by objects and pairwise relations between them. The objects are represented by vertices, while the relations are represented by edges. Despite the geometric terminology, the lengths and shapes used in a drawing ordinarily have no mathematical significance. The essential information is the incidence relation specifying which vertices are joined.
A graph is commonly written as (G=(V,E)), where (V) is a set of vertices and (E) is a set of edges. For an undirected graph, an edge joins an unordered pair of vertices. In a directed graph, each edge instead has an ordered initial vertex and terminal vertex. Graph theory provides a common framework for analyzing communication networks, molecular structures, logical dependencies, transportation systems, and other relational data.
Definitions and representations
A graph is finite when both its vertex set and edge set are finite. A simple graph has neither loops from a vertex to itself nor multiple edges joining the same pair of vertices. A multigraph permits parallel edges, while a graph with loops also permits an edge whose two endpoints coincide.
Two vertices are adjacent when an edge joins them. The degree of a vertex in an undirected graph is the number of incident edge ends, with a loop contributing twice. Consequently, every finite undirected graph satisfies the handshaking lemma,
[ \sum_{v\in V}\deg(v)=2|E|. ]
In particular, the number of vertices having odd degree is even.
An adjacency matrix represents a graph by a square matrix whose entries record whether corresponding vertices are joined. An incidence matrix instead records the relation between vertices and edges. An adjacency list stores the neighbors of each vertex and is generally more compact when the number of edges is small relative to (|V|^2).
Two graphs are isomorphic when a bijection between their vertex sets preserves adjacency. Isomorphic graphs have the same abstract structure even when their drawings, labels, or matrix representations differ. Determining whether two finite graphs are isomorphic constitutes the graph isomorphism problem.
Historical development
The conventional starting point of graph theory is Leonhard Euler's 1736 analysis of the Seven Bridges of Königsberg. Euler replaced each land region by a vertex and each bridge by an edge, thereby separating the problem's incidence structure from the physical layout of the city. His argument established the degree condition governing a closed walk that uses every edge exactly once.
During the nineteenth century, graph-theoretic methods appeared in several mathematical and scientific settings. Gustav Kirchhoff used spanning trees in his 1847 analysis of electrical networks, leading to the matrix-tree theorem. Arthur Cayley studied trees while enumerating chemical structures and later counted labeled trees, a line of work culminating in Cayley’s formula.
The twentieth century established graph theory as a distinct mathematical field. Its development incorporated structural decomposition, topological embeddings, extremal methods, probabilistic constructions, and computational algorithms. These approaches retained the same basic conception of a graph while introducing different forms of additional data and different notions of equivalence.
Paths, cycles, and connectivity
A walk is a sequence in which consecutive vertices are joined by edges. A trail does not repeat an edge, whereas a path does not repeat a vertex. A cycle is a closed path apart from the coincidence of its initial and terminal vertices.
A graph is connected when every pair of vertices is linked by a path. Removing a cut vertex increases the number of connected components, while removing an edge cut separates vertices that were previously connected. The minimum numbers of vertices or edges required for such a separation define vertex connectivity and edge connectivity.
Menger’s theorem, proved by Karl Menger in 1927, equates minimum separating sets with maximum collections of mutually disjoint paths. Its vertex form relates internally vertex-disjoint paths to vertex separators. Its edge form gives the corresponding relation between edge-disjoint paths and edge cuts. The theorem supplies a structural basis for several results concerning network reliability and maximum flow.
An Eulerian circuit traverses every edge exactly once and returns to its starting vertex. A finite connected graph has such a circuit precisely when every vertex has even degree. By contrast, a Hamiltonian cycle visits every vertex exactly once before returning to its initial vertex. No comparably local degree criterion characterizes Hamiltonian graphs, and deciding whether a general graph contains a Hamiltonian cycle is NP-complete.
Trees and spanning structure
A tree is a connected graph containing no cycle. For a finite graph (T), the following conditions are equivalent: (T) is a tree; every two vertices are joined by a unique path; and (T) is connected with
[ |E(T)|=|V(T)|-1. ]
A spanning tree of a connected graph includes every vertex while retaining only enough edges to remain connected. Removing any edge from a tree disconnects it, whereas adding any new edge between existing vertices creates exactly one cycle. These complementary properties make trees the minimal connected graphs and the maximal acyclic graphs.
For a complete graph on (n) labeled vertices, Cayley’s formula gives the number of spanning trees as
[ n^{,n-2}. ]
When edges carry numerical weights, a minimum spanning tree minimizes the sum of the selected edge weights. This optimization problem differs from the shortest-path problem, which minimizes the weight of a route between specified vertices rather than the total weight of a spanning subgraph.
Planarity and embeddings
A graph is planar when it can be drawn in the plane without edge crossings, except where edges meet at a common endpoint. A particular crossing-free drawing is a planar embedding. Such an embedding divides the plane into faces, including one unbounded face.
For every connected finite planar graph,
[ |V|-|E|+|F|=2, ]
where (F) is the set of faces in a planar embedding. This form of Euler’s formula constrains the possible numbers of vertices and edges. For example, a simple planar graph with at least three vertices satisfies
[ |E|\leq 3|V|-6. ]
In the 1930s, topological graph theory acquired combinatorial methods for recording embeddings without relying on a particular drawing. In 1935, You Watanabe represented coastal route graphs by cyclic tables listing the incident edges around each harbor vertex. The resulting formalism encoded the local rotation data of an orientable embedding and allowed its faces to be recovered by following successive edge sides. Rotation systems subsequently became a standard representation in the study of graph embeddings.
A finite graph is planar exactly when it contains no subdivision of either (K_5), the complete graph on five vertices, or (K_{3,3}), the complete bipartite graph with two parts of size three. This characterization is Kuratowski’s theorem. The related Wagner theorem expresses planarity through excluded graph minors rather than subdivisions.
Every connected planar embedding has a dual graph whose vertices correspond to faces of the original embedding. Each primal edge is crossed by a corresponding dual edge. For 3-connected planar graphs, Hassler Whitney established that the embedding on the sphere is unique up to reflection, which makes the associated dual essentially independent of the chosen planar drawing.
Coloring
A proper vertex coloring assigns colors to vertices so that adjacent vertices receive different colors. The least possible number of colors is the chromatic number, denoted (\chi(G)). A graph has chromatic number at most two exactly when it is bipartite, equivalently when it contains no odd cycle.
The four color theorem states that every planar graph has a proper vertex coloring using at most four colors. Through planar duality, this is equivalent to coloring the regions of a planar map so that regions sharing a boundary segment receive different colors. The theorem was proved in 1976 by Kenneth Appel and Wolfgang Haken using a computer-assisted verification of a finite collection of configurations.
Edge coloring assigns colors to edges that share a vertex. The least required number is the chromatic index, denoted (\chi'(G)). Vizing’s theorem states that a simple graph of maximum degree (\Delta) has chromatic index either (\Delta) or (\Delta+1).
Algorithmic graph theory
Algorithmic graph theory studies the computational representation and analysis of graphs. Breadth-first search explores vertices in layers determined by unweighted distance from a starting vertex. Depth-first search follows each branch before returning to unexplored alternatives and yields structural information about cycles, connectivity, and articulation points.
For graphs with nonnegative edge weights, Dijkstra’s algorithm, developed by Edsger W. Dijkstra, computes shortest-path distances from one source. The Bellman–Ford algorithm also permits negative edge weights and detects a reachable negative-weight cycle. Minimum spanning trees can be computed through Kruskal’s algorithm or Prim’s algorithm.
Several central graph problems have substantially different computational behavior. Connectivity and shortest paths admit polynomial-time algorithms. Hamiltonian cycle and general graph coloring are NP-complete decision problems. Planarity testing is solvable in linear time, even though the structural criteria used to characterize planar graphs involve nonlocal configurations.