Graph Theory — The Mathematics of Connections
Graph theory studies networks — collections of points (vertices) connected by lines (edges). It began with a simple question about bridges in Königsberg and grew into one of the most applied branches of mathematics. Social networks, the internet, transportation, epidemiology, circuit design, and even the structure of molecules are all graphs. And at its frontier lies the most famous unsolved problem in computer science: P vs NP.
🔗 Graphs — Vertices, Edges, and the Bridges of Königsberg
Basic Vocabulary
Consequence: Every graph has an even number of vertices of odd degree. This is why Euler's seven bridges had an odd number of odd-degree vertices — making a Eulerian circuit impossible.
Paths, Cycles, and Connectedness
A path is a sequence of edges where no vertex repeats. A cycle is a closed path. A graph is connected if there's a path between every pair of vertices. A tree is a connected graph with no cycles — it has exactly n−1 edges for n vertices. Trees are the minimal connected structures and appear everywhere: file systems, decision trees, family trees, spanning trees of networks.
🎨 Graph Coloring — How Many Colors Do You Need?
Greedy Coloring Algorithm
Order the vertices. Give each vertex the smallest color not used by its already-colored neighbors. In the worst case, this uses at most Δ+1 colors (where Δ is the maximum degree). Brooks' theorem gives a tighter bound: for connected graphs that aren't complete or odd cycles, χ(G) ≤ Δ.
Planar Graphs — Drawing Without Crossings
A graph is planar if it can be drawn in the plane with no edges crossing. Euler's formula for connected planar graphs:
⚡ Matchings and Flows — Connecting Pairs and Moving Stuff
Maximum Matching
A matching is a set of edges with no shared vertices. A maximum matching contains as many edges as possible. The augmenting path algorithm finds one: start with any matching, find a path that alternates between unmatched and matched edges, flip the edges along the path to increase the matching size. Repeat until no augmenting path exists — then the matching is maximum.
Example: In a graph with 4 jobs and 4 applicants, if the maximum matching has size 3, then there are 3 vertices that together touch every possible edge. Those 3 vertices form a bottleneck — explaining why 4 matches are impossible.
Network Flows — The Max-Flow Min-Cut Theorem
A flow network is a directed graph with a source (s), a sink (t), and capacities on edges. A flow sends as much "stuff" from s to t as possible without exceeding capacities. The max-flow min-cut theorem says the maximum flow equals the minimum capacity of a cut (a set of edges whose removal disconnects s from t). This is one of the most applied results in mathematics — it governs traffic flow, internet routing, airline scheduling, and the movement of goods in supply chains.
🌍 Deep Graph Theory — Ramsey, Random Graphs, and P vs NP
Extremal Graph Theory — Turán's Theorem
What's the maximum number of edges in a graph on n vertices that contains no triangle? Turán's theorem answers: the extremal graph is a complete bipartite graph with parts as equal as possible — ⌊n²/4⌋ edges. More generally, if a graph has no Kᵣ as a subgraph, the extremal number is given by the Turán graph T(n, r−1).
Random Graphs — The Erdős–Rényi Model
In the G(n,p) model, each of the n(n−1)/2 possible edges appears independently with probability p. This seems random, but it produces remarkably predictable behavior. At p = 1/n, the graph undergoes a phase transition: below this threshold, components are tiny (O(log n)); above it, a giant component emerges containing a constant fraction of vertices. This models how epidemics spread, how social networks form, and how the internet connected — suddenly, not gradually.
Graph Algorithms — P vs NP
Many graph problems have efficient (polynomial-time) algorithms: finding shortest paths (Dijkstra), minimum spanning trees (Kruskal), maximum matchings, network flows. These are in P. But others seem to require checking all possibilities: finding a Hamiltonian cycle (a tour visiting each vertex once), the traveling salesman problem, graph coloring with 3 colors, finding a clique of a given size. These are in NP — solutions can be checked quickly, but finding them seems hard. The P vs NP question asks whether these are truly distinct: can every problem whose solution is easy to verify also be solved quickly? A $1M Clay Millennium problem, and arguably the most important open question in computer science.
🎯 Practice — Check Your Graph Intuition
These puzzles build graph theory intuition — no code needed.
Graph Minors and the Robertson–Seymour Theorem
The Robertson–Seymour theorem, proved over a series of twenty papers from 1983 to 2004, states that the class of all finite graphs is well‑quasi‑ordered by the minor relation. In concrete terms, for any infinite sequence of graphs G₁, G₂, … there exist indices i < j such that Gᵢ is a minor of Gⱼ. A minor is obtained by deleting vertices, deleting edges, and contracting edges. This deep structural result has two immediate consequences that appear repeatedly in competitive examinations.
First, any minor‑closed family of graphs (a family closed under taking minors) can be characterized by a finite set of forbidden minors. For planar graphs the forbidden set is {K₅, K₃,₃}; for graphs embeddable on the torus the set contains 16 241 graphs; for linklessly embeddable graphs the forbidden set is the seven Petersen‑family graphs. Examiners often ask: “Which of the following graphs is a forbidden minor for the class of graphs with treewidth at most two?” The answer is K₄, because treewidth ≤ 2 exactly excludes K₄ as a minor.
Second, the theorem yields an algorithmic meta‑theorem: for any fixed graph H, testing whether H is a minor of an input graph G can be done in cubic time O(|V(G)|³). Combined with the finite forbidden‑minor characterization, this gives polynomial‑time algorithms for every minor‑closed property. However, the constant hidden in the O‑notation depends astronomically on |V(H)|, so the result is primarily of theoretical interest. In practice, examiners test the conceptual implication: “If a graph property is minor‑closed, does there always exist a polynomial‑time recognition algorithm?” The correct answer is yes, by the Robertson–Seymour theorem, even though the algorithm may be impractical.
Key Points for Revision
- Well‑quasi‑ordering ⇒ finite forbidden‑minor set for every minor‑closed class.
- Planar graphs: forbidden minors K₅ and K₃,₃ (Kuratowski’s theorem is the special case).
- Minor testing for fixed H is O(n³); the constant is non‑elementary in |V(H)|.
- Applications: treewidth ≤ k ⇔ exclude a (k+2)‑clique minor; linkless embeddability ⇔ exclude Petersen family.
Spectral Graph Theory — Eigenvalues and Expansion
Spectral graph theory studies the eigenvalues of matrices associated with a graph, principally the adjacency matrix A and the Laplacian matrix L = D − A, where D is the diagonal degree matrix. For a d‑regular graph the adjacency eigenvalues lie in [−d, d]; the largest eigenvalue is d with eigenvector 1. The second largest eigenvalue λ₂ controls many combinatorial properties.
The Cheeger inequality links λ₂ to the edge expansion (conductance) h(G) = minS⊂V, 0<|S|≤|V|/2 |∂S| / (d|S|). For d‑regular graphs it states: (d − λ₂)/2 ≤ h(G) ≤ √(2d(d − λ₂)). A small spectral gap d − λ₂ implies the existence of a sparse cut; a large gap certifies that the graph is an expander. Examiners frequently ask to bound the expansion of a given regular graph when λ₂ is known, or to deduce that a family of graphs with λ₂ ≤ d − ε forms an expander family.
Ramanujan graphs are d‑regular graphs whose non‑trivial eigenvalues satisfy |λ| ≤ 2√(d−1). They achieve the optimal spectral gap given by the Alon–Boppana bound: for any infinite family of d‑regular graphs, lim inf λ₂ ≥ 2√(d−1). Constructions by Lubotzky–Phillips–Sarnak and by Margulis provide explicit Ramanujan graphs for infinitely many degrees. In competitive exams, a typical question is: “Show that a 3‑regular Ramanujan graph has λ₂ ≤ 2√2 ≈ 2.828.” The answer follows directly from the definition.
The Laplacian eigenvalues 0 = μ₁ ≤ μ₂ ≤ … ≤ μₙ give an alternative expansion measure. The second Laplacian eigenvalue μ₂ (algebraic connectivity) satisfies μ₂ = d − λ₂ for regular graphs. The same Cheeger inequality can be written as μ₂/2 ≤ h(G) ≤ √(2d μ₂). This formulation extends naturally to irregular graphs, where the normalized Laplacian ℒ = I − D⁻¹ᐟ² A D⁻¹ᐟ² is used.
Key Points for Revision
- Adjacency eigenvalues of d‑regular graphs lie in [−d, d]; λ₁ = d.
- Cheeger inequality: (d − λ₂)/2 ≤ h(G) ≤ √(2d(d − λ₂)).
- Ramanujan graphs: |λ| ≤ 2√(d−1) for all non‑trivial eigenvalues.
- Alon–Boppana bound: lim inf λ₂ ≥ 2√(d−1) for any infinite d‑regular family.
- Laplacian μ₂ = d − λ₂ (regular case); normalized Laplacian for irregular graphs.
Graph Homomorphisms and the Chromatic Polynomial
A graph homomorphism from G to H is a vertex map φ: V(G) → V(H) such that every edge uv ∈ E(G) maps to an edge φ(u)φ(v) ∈ E(H). When H = Kₖ, a homomorphism is exactly a proper k‑coloring of G. The number of homomorphisms from G to Kₖ is a polynomial in k, called the chromatic polynomial P_G(k). It satisfies the deletion–contraction recurrence: for any edge e, P_G(k) = PG−e(k) − PG/e(k), with base cases PEₙ(k) = kⁿ for the edgeless graph on n vertices and PK₂(k) = k(k−1).
The chromatic polynomial encodes rich information. Its degree is |V(G)|, its leading coefficient is 1, and the coefficient of k|V|−1 is −|E(G)|. The roots of P_G(k) (chromatic roots) are algebraic integers; a famous theorem of Thomassen shows that chromatic roots are dense in the complex plane, but for real roots they are bounded above by the maximum degree plus one. The value P_G(−1) equals (−1)|V| times the number of acyclic orientations of G (Stanley’s theorem). Examiners often ask: “Compute PCₙ(k) for the cycle Cₙ.” Using deletion–contraction repeatedly yields PCₙ(k) = (k−1)ⁿ + (−1)ⁿ(k−1).
Graph homomorphisms generalize coloring. The homomorphism order (G → H) forms a lattice; the core of a graph is its minimal homomorphic image. Determining whether G → H exists is NP‑complete for general H (Hell–Nešetřil theorem), but polynomial for bipartite H. In parameterized complexity, the problem is fixed‑parameter tractable when parameterized by the treewidth of G, a direct application of Courcelle’s theorem.
Key Points for Revision
- Chromatic polynomial P_G(k) counts proper k‑colorings; degree = |V|, leading coeff = 1.
- Deletion–contraction: P_G = PG−e − PG/e.
- Cycle formula: PCₙ(k) = (k−1)ⁿ + (−1)ⁿ(k−1).
- Stanley: P_G(−1) = (−1)|V|·(# acyclic orientations).
- Hell–Nešetřil: H‑coloring is NP‑complete unless H is bipartite or has a loop.
Treewidth, Parameterized Complexity, and Algorithmic Graph Minor Theory
Treewidth measures how close a graph is to a tree. A tree decomposition of G is a pair (T, {X_t}t∈V(T)) where T is a tree and each bag X_t ⊆ V(G) satisfies: (1) ∪_t X_t = V(G); (2) for every edge uv ∈ E(G) some bag contains both u and v; (3) for each vertex v, the bags containing v form a connected subtree of T. The width is max_t |X_t| − 1; the treewidth tw(G) is the minimum width over all decompositions. Trees have treewidth 1; cycles have treewidth 2; the k×k grid has treewidth k.
Robertson and Seymour proved that for every fixed k, the class of graphs with treewidth ≤ k is minor‑closed and characterized by a finite set of forbidden minors (the (k+2)‑clique is one of them). This yields a cubic‑time algorithm to test treewidth ≤ k, but the constant is huge. In practice, competitive exams focus on the algorithmic consequence: many NP‑hard problems become linear‑time solvable on graphs of bounded treewidth via dynamic programming on a tree decomposition. Courcelle’s theorem (1990) states that any graph property expressible in monadic second‑order logic (MSO₂) can be decided in linear time on graphs of bounded treewidth. Examples: Hamiltonian cycle, 3‑coloring, dominating set, Steiner tree.
Parameterized complexity refines this picture. A problem is fixed‑parameter tractable (FPT) with parameter k if it can be solved in time f(k)·nO(1). Treewidth is a central parameter: many problems are FPT when parameterized by treewidth, but W[1]‑hard when parameterized by solution size (e.g., clique). The Exponential Time Hypothesis (ETH) implies that no algorithm can solve 3‑SAT in 2o(n) time; this transfers to lower bounds for treewidth‑based algorithms, e.g., Hamiltonian cycle cannot be solved in 2o(tw)·nO(1) unless ETH fails.
Key Points for Revision
- Treewidth definition via tree decomposition; width = max bag size − 1.
- Forbidden minors for tw ≤ k include Kk+2; grid minor theorem: large treewidth ⇒ large grid minor.
- Courcelle’s theorem: MSO₂ properties linear‑time on bounded treewidth.
- Dynamic programming on tree decompositions yields O(2tw·n) algorithms for many problems.
- ETH lower bounds: no 2o(tw)·nO(1) for Hamiltonian cycle, etc.
Graph Limits and Graphons — The Analytic View of Large Networks
The theory of dense graph limits, developed by Lovász, Szegedy, Borgs, Chayes, and Sós, provides an analytic framework for sequences of graphs whose edge density stays bounded away from zero. A graphon is a symmetric measurable function W: [0,1]² → [0,1]. Every finite graph G on n vertices corresponds to a step‑function graphon W_G obtained by partitioning [0,1] into n equal intervals and setting W_G(x,y) = 1 if the corresponding vertices are adjacent, 0 otherwise. The cut distance δ_□(W₁,W₂) = supS,T⊆[0,1] |∫S×T (W₁−W₂)| metrizes the space of graphons modulo measure‑preserving bijections.
A sequence of graphs (G_n) converges if the homomorphism densities t(F,G_n) = hom(F,G_n)/|V(G_n)||V(F)| converge for every fixed graph F. The limit object is a graphon W such that t(F,W) = lim t(F,G_n). This is the dense analogue of the Benjamini–Schramm local convergence for sparse graphs. The Szemerédi regularity lemma is equivalent to the statement that every graphon can be approximated in cut distance by a step function with a bounded number of steps.
Applications include property testing: a graph property is testable with constant queries iff it is characterized by a finite set of subgraph density constraints (Alon–Shapira). In extremal combinatorics, the limit framework yields analytic proofs of Turán‑type results; for example, the maximum edge density of a triangle‑free graph is 1/2, attained by the bipartite graphon W(x,y) = 1x≤1/2<y or y≤1/2<x</sub>. Examiners may ask: “What is the limit graphon of the sequence of complete bipartite graphs K⌊n/2⌋,⌈n/2⌉?” The answer is the bipartite graphon described above.
Key Points for Revision
- Graphon: symmetric measurable W: [0,1]² → [0,1]; step functions represent finite graphs.
- Cut distance δ_□ metrizes convergence; homomorphism densities t(F,G) converge ⇔ graphon limit exists.
- Szemerédi regularity lemma ⇔ graphons approximable by bounded‑step functions.
- Testable properties ⇔ finite subgraph density constraints (Alon–Shapira).
- Triangle‑free extremal limit: bipartite graphon with density 1/2.
- Confusing minor‑closed with subgraph‑closed; minor‑closed families have finite forbidden minors, subgraph‑closed families need not.
- Assuming Cheeger inequality gives exact expansion; it only provides bounds, and the upper bound can be trivial (≤1).
- Thinking chromatic polynomial roots are always integers; they are algebraic integers, often non‑real.
- Believing Courcelle’s theorem gives practical algorithms; the hidden constant is non‑elementary in the formula size.
- Treating graphons as only for dense graphs; sparse limits require different tools (local weak convergence).
- Forgetting that the grid minor theorem is qualitative — the function relating treewidth to grid size is not polynomial.
- Review these traps before the exam.