Skip to content
Graph BasicsGraph ColoringMatchings & FlowsRamsey TheoryPractice ProblemsnextnextnextnextDef: Graph = (V, E)Art. 243G: Local governance networksvlymbooq
Graph Theory Concepts Applied to Governance Revision Diagram — Shows the logical progression from basic graph elements to advanced topics and practice. · Open the full diagram →
🔬 Scientist Pure mathematics — no exam syllabus

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.

"Graph theory is the science of relationships. Everything is connected to everything else — graph theory makes that precise."
— Anonymous

🔗 Graphs — Vertices, Edges, and the Bridges of Königsberg

How Seven Bridges Launched a Mathematical Revolution
In the 18th century, the city of Königsberg had seven bridges crossing the Pregel River. The question: could you take a walk that crossed each bridge exactly once and return to your starting point? In 1736, Euler proved it was impossible — and in doing so, invented graph theory. He realized the problem wasn't about geography; it was about connections. The landmasses became vertices, the bridges became edges, and the answer depended only on the degrees of the vertices. A graph has an Eulerian circuit (a tour using every edge exactly once) iff every vertex has even degree. All seven Königsberg bridges had odd degree — impossible.
Sometimes the deepest insights come from ignoring what something is and focusing only on how it's connected.

Basic Vocabulary

Degree
deg(v) = # edges incident to v
Handshaking Lemma
Σ deg(v) = 2|E|
Complete Graph Kₙ
Every pair connected
Bipartite Graph
Two sets, edges only between
✨
The Handshaking Lemma ▶
The sum of all vertex degrees equals twice the number of edges. Why? Each edge contributes 1 to the degree of each of its two endpoints, so it contributes 2 to the total sum.

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.

Properties of Trees
A tree on n vertices has exactly n−1 edges
Add one more edge → creates a cycle. Remove one edge → disconnects the graph.

🎨 Graph Coloring — How Many Colors Do You Need?

A 124-Year Obsession That Changed Mathematics
In 1852, Francis Guthrie noticed that four colors sufficed to color any map of England so that adjacent counties had different colors. The question: is four always enough? The Four Color Theorem says yes — any planar graph (one that can be drawn without crossing edges) is 4-colorable. It was the first major theorem proven by computer (Appel and Haken, 1976), sparking controversy about what constitutes a proof. A graph's chromatic number χ(G) is the fewest colors needed. For Kₙ, χ = n. For bipartite graphs, χ = 2. For planar graphs, χ ≤ 4.
Sometimes a simple question takes over a century and a computer to answer.

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:

Euler's Formula for Planar Graphs
V − E + F = 2
Vertices minus edges plus faces equals 2 (for connected planar graphs).
Consequences of Euler's Formula
For a planar graph with V ≥ 3: E ≤ 3V − 6. This is why K₅ (complete graph on 5 vertices) is non-planar — it has 10 edges, but 3×5−6 = 9, so it violates the bound. K₃,₃ (utility graph) also violates a face-length bound and is non-planar. Kuratowski's theorem says a graph is planar iff it contains no subdivision of K₅ or K₃,₃.

⚡ Matchings and Flows — Connecting Pairs and Moving Stuff

Hall's Marriage Theorem and the Perfect Match
Suppose you have n jobs and n applicants, and each applicant is qualified for some subset of jobs. Can you assign each applicant a unique job they're qualified for? This is a matching problem on a bipartite graph. Hall's marriage theorem answers: a perfect matching exists iff for every subset of applicants, the set of jobs they collectively qualify for is at least as large. This simple condition appears in assignment problems, scheduling, and even online dating algorithms.
A graph doesn't need to be dense — it just needs enough connections for everyone to find a partner.

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.

✨
König's Theorem — Matchings and Covers ▶
In bipartite graphs, the size of a maximum matching equals the size of a minimum vertex cover (a set of vertices that touches every edge). This is König's theorem, and it's a special case of the max-flow min-cut theorem.

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.

Max-Flow Min-Cut Theorem
Maximum flow = Minimum cut capacity
The bottleneck determines the throughput. The Ford-Fulkerson algorithm finds the max flow by repeatedly finding augmenting paths.

🌍 Deep Graph Theory — Ramsey, Random Graphs, and P vs NP

Ramsey Theory: Complete Disorder Is Impossible
In any group of 6 people, there must be either 3 mutual friends or 3 mutual strangers. This is R(3,3) = 6 — the smallest number where a monochromatic triangle is unavoidable. Ramsey theory says that in any large enough structure, patterns inevitably emerge. R(4,4) = 18, but R(5,5) is unknown — only that it's between 43 and 48. The Ramsey numbers grow extremely fast, and computing them is one of the hardest problems in combinatorics. The philosopher Wittgenstein famously tried to disprove R(3,3) = 6 by drawing a counterexample — and failed.
Complete randomness is impossible. Enough structure always contains order.

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).

Mantel's Theorem (r=3)
A triangle-free graph on n vertices has at most ⌊n²/4⌋ edges. Example: n = 6. Max edges without a triangle = 9 (a complete bipartite K₃,₃). If you add one more edge, a triangle appears. This is the simplest case of Turán's theorem.

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.

Erdős–Rényi Phase Transition
At p = 1/n, a giant component suddenly appears
Below: isolated trees. Above: a single component containing most vertices. This critical point is remarkably sharp.

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.

"Graph theory is the ultimate applied mathematics — it doesn't matter whether you're studying molecules or social networks, it's all graphs underneath."
— Paul Erdős

🎯 Practice — Check Your Graph Intuition

These puzzles build graph theory intuition — no code needed.

← Back to Math Map

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.
Technique: Applying Cheeger Inequality to Bound Expansion
A 4‑regular graph on 100 vertices has second adjacency eigenvalue λ₂ = 2.5. Estimate the edge expansion h(G) using the Cheeger inequality.
For a d‑regular graph, Cheeger gives (d − λ₂)/2 ≤ h(G) ≤ √(2d(d − λ₂)). Here d = 4, λ₂ = 2.5, so d − λ₂ = 1.5. Lower bound = 1.5/2 = 0.75. Upper bound = √(2·4·1.5) = √12 ≈ 3.464. Since h(G) ≤ 1 by definition (maximum possible cut fraction), the effective upper bound is 1. Thus 0.75 ≤ h(G) ≤ 1. The graph is a reasonably good expander.
Exam‑Day Strategy
Memorize the exact form of the Cheeger inequality for both adjacency and Laplacian spectra. When a problem gives λ₂ or μ₂, immediately write the two‑sided bound; the lower bound often yields a quick “expander” conclusion, while the upper bound is useful for proving non‑expansion. Also remember that Ramanujan graphs are the only explicit constructions achieving the Alon–Boppana limit — this fact appears in multiple‑choice questions about optimal spectral gap.

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.