Graph Theory
Graph theory is the mathematical study of graphs, which are structures made of vertices (dots) connected by edges (lines), used to model networks and relationships.
Definition
Graph theory studies diagrams made of dots (vertices) connected by lines (edges), diagrams that model all kinds of networks: friend connections, road maps, the internet. Formally, a graph $G = (V, E)$ consists of a vertex set $V$ and an edge set $E$ of pairs of vertices, and can be directed (edges have direction) or undirected; key concepts include the degree of a vertex, connected components, cycles, paths, and spanning trees. More formally, $E \subseteq V \times V$ (directed) or $E \subseteq \{\{u,v\}: u,v \in V\}$ (undirected); graph theory intersects combinatorics, algebra (spectral graph theory uses eigenvalues of the adjacency matrix), topology (graph embeddings on surfaces), and algorithms (graph isomorphism relates to P vs. NP).
Example
Imagine a map of cities (vertices) connected by roads (edges): graph theory answers questions like "What is the shortest route from city A to city B?" The Seven Bridges of Konigsberg asked whether you could cross all $7$ bridges exactly once; Euler proved it impossible in 1736, founding graph theory, showing a graph has an Euler path iff exactly $0$ or $2$ vertices have odd degree. The Four Color Theorem, that every planar graph can be colored with $4$ colors so no adjacent vertices share a color, was proved in 1976 by Appel and Haken using computer verification of $1{,}936$ cases.
Key Insight
Any time things are connected, graph theory applies: social networks, circuit boards, flight routes, and family trees are all graphs, and Euler's solution to the Bridges problem introduced graph traversal, which today underlies GPS navigation, web crawling, and network routing. Spectral graph theory uses the eigenvalues of the Laplacian to study connectivity, diffusion, and random walks on graphs, with applications in machine learning (graph neural networks).