Graph Theory
Calculus & Advanced MathGraph 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 (called vertices) connected by lines (called edges). These diagrams model all kinds of networks: friend connections, road maps, the internet.
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?"
Key Insight
Any time things are connected, graph theory applies. Social networks, circuit boards, flight routes, and family trees are all graphs.
Definition
A graph $G = (V, E)$ consists of a vertex set $V$ and an edge set $E$ of pairs of vertices. Graphs can be directed (edges have direction) or undirected. Key concepts: degree of a vertex (number of edges), connected components, cycles, paths, and spanning trees.
Example
The Seven Bridges of Konigsberg: can you cross all $7$ bridges exactly once? Euler proved it impossible, creating graph theory in 1736. The key insight: a graph has an Euler path iff exactly $0$ or $2$ vertices have odd degree.
Key Insight
Euler's solution to the Bridges problem introduced the concept of graph traversal, which today underlies algorithms for navigation (GPS), web crawling, and network routing.
Definition
Formally, a graph $G = (V, E)$ where $E \subseteq V \times V$ (for directed) or $E \subseteq \{\{u,v\}: u,v \in V\}$ (for undirected). Graph theory intersects combinatorics, algebra (spectral graph theory uses eigenvalues of the adjacency matrix), topology (graph embeddings on surfaces), and algorithms (P vs. NP relates to graph isomorphism).
Example
Four Color Theorem: every planar graph can be colored with $4$ colors such that no adjacent vertices share a color. Proved in 1976 by Appel and Haken using computer verification of $1{,}936$ cases.
Key Insight
The chromatic polynomial of a graph counts its proper colorings. 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).