Detailed slide-by-slide text content extracted from this presentation.
Slide 01
Graph Theory
- The Mathematics of Connection
- Graph theory studies discrete structures made of vertices (nodes) and edges (links). Born from a puzzle about bridges in 1736, it now underpins social networks, internet routing, compiler optimization, epidemiology, and nearly every algorithmic challenge in computer science.
- This deck covers the foundations, classical results, algorithms, and modern applications of graph theory.
Slide 02
Origins: The Bridges of Konigsberg
- In 1736, Leonhard Euler proved it was impossible to walk through the city of Konigsberg crossing each of its seven bridges exactly once. His proof -- that such a walk requires at most two vertices of odd degree -- created graph theory as a discipline.
- "This question... does not belong to geometry, nor to algebra, nor to any other mathematical discipline yet known. It belongs to the geometry of position."
- -- Leonhard Euler, "Solutio problematis ad geometriam situs pertinentis" (1736)
- Euler abstracted the physical layout into a graph: four landmasses as vertices, seven bridges as edges. The specific distances and shapes were irrelevant -- only connectivity mattered.
Slide 03
Fundamental Definitions
- Basic Elements
- Graph G = (V, E) -- vertex set V, edge set E
- Edge {u,v} connects vertices u and v
- Degree deg(v): number of edges incident to v
- Order |V| and size |E| of a graph
- Adjacent: two vertices sharing an edge
- Variations
- Directed graph (digraph): edges have direction (u->v)
- Weighted graph: edges carry numerical values
- Multigraph: allows parallel edges between same pair
- Hypergraph: edges can connect 3+ vertices
- Simple graph: no loops or parallel edges
Slide 04
The Handshaking Lemma
- The first theorem of graph theory, also due to Euler:
- In any graph, the sum of all vertex degrees equals twice the number of edges: Sum(deg(v)) = 2|E|
- Immediate corollary: the number of vertices with odd degree is always even. This seemingly simple fact has profound consequences:
- A graph has an Eulerian circuit iff every vertex has even degree
- Used to prove impossibility of certain network designs
- Basis for degree-sequence characterization (Erdos-Gallai theorem)
- In any social network, the number of people with an odd number of friends is even
Slide 05
Special Graph Families
- Complete Graph K_n
- Every pair connected. n(n-1)/2 edges. K_5 is the smallest non-planar complete graph. Models full connectivity.
- Bipartite Graph
- Vertices partition into two sets; edges only between sets. Characterized by having no odd cycles (Konig, 1936). Models matching problems.
- Tree
- Connected acyclic graph. |E| = |V| - 1. Unique path between any two vertices. n^(n-2) labeled trees on n vertices (Cayley's formula).
- Planar Graph
- Can be drawn in the plane with no edge crossings. Must satisfy |E|
Slide 06
Paths, Cycles, and Connectivity
- Definitions
- Walk: sequence of vertices where consecutive pairs are adjacent
- Path: walk with no repeated vertices
- Cycle: closed path (start = end, length >= 3)
- Connected: path exists between every pair of vertices
- Component: maximal connected subgraph
- Connectivity Measures
- Vertex connectivity kappa(G): min vertices to disconnect
- Edge connectivity lambda(G): min edges to disconnect
- Whitney's theorem: kappa(G) k-connected: remains connected after removing any k-1 vertices
- Menger's theorem: relates connectivity to independent paths
Slide 07
Trees and Spanning Trees
- Trees are the "minimal connected" graphs -- removing any edge disconnects them. Every connected graph contains a spanning tree.
- Properties of Trees
- Unique path between any two vertices. Adding any edge creates exactly one cycle. |E| = |V| - 1. Equivalent: connected and acyclic; connected with exactly n-1 edges; acyclic with exactly n-1 edges.
- Cayley's Formula
- The number of labeled trees on n vertices is n^(n-2). For n=4: 16 distinct labeled trees. Proved elegantly by Prufer sequences (bijection with integer sequences).
- Minimum Spanning Tree
- Spanning tree of minimum total weight. Kruskal's: O(E log E), greedy by weight. Prim's: O(E + V log V) with Fibonacci heap. Both greedy, both optimal.
Slide 08
Graph Traversal Algorithms
- Breadth-First Search (BFS)
- Explores level by level using a queue
- Time: O(V + E), Space: O(V)
- Finds shortest paths in unweighted graphs
- Applications: connected components, bipartiteness testing, web crawling
- Produces a BFS tree (spanning tree)
- Depth-First Search (DFS)
- Explores as deep as possible, then backtracks
- Time: O(V + E), Space: O(V)
- Classifies edges: tree, back, forward, cross
- Applications: cycle detection, topological sort, strongly connected components
- Back edges indicate cycles in the graph
Slide 09
Shortest Path Algorithms
- AlgorithmTypeComplexityConstraints
- BFSSingle-sourceO(V + E)Unweighted only
- DijkstraSingle-sourceO(E + V log V)Non-negative weights
- Bellman-FordSingle-sourceO(VE)Detects negative cycles
- Floyd-WarshallAll-pairsO(V^3)Any weights, no neg cycles
- Johnson'sAll-pairsO(V^2 log V + VE)Reweighting technique
- A*Single-pairO(E) typicalRequires admissible heuristic
- Dijkstra's algorithm (1959) remains the workhorse of navigation systems, processing billions of queries daily in Google Maps and similar services.
Slide 10
Euler and Hamilton Paths
- Eulerian
- Eulerian circuit: traverse every edge exactly once, return to start
- Exists iff graph is connected and all vertices have even degree
- Eulerian path: exists iff exactly 0 or 2 vertices have odd degree
- Finding one: O(E) via Hierholzer's algorithm
- Applied in DNA sequencing (de Bruijn graphs)
- Hamiltonian
- Hamiltonian cycle: visit every vertex exactly once, return to start
- No simple characterization (unlike Eulerian)
- Decision problem is NP-complete
- Sufficient conditions: Dirac (deg >= n/2), Ore (deg(u)+deg(v) >= n)
- Traveling Salesman Problem: find minimum-weight Hamiltonian cycle
Slide 11
Planar Graphs
- A graph is planar if it can be embedded in the plane without edge crossings. Planarity has deep connections to topology and efficient algorithms.
- Euler's formula for connected planar graphs: V - E + F = 2 (V=vertices, E=edges, F=faces)
- Corollary: E = 3)
- Kuratowski's theorem (1930): G is planar iff it contains no subdivision of K_5 or K_{3,3}
- Wagner's theorem: equivalent formulation using graph minors
- Four Color Theorem (1976): every planar graph is 4-colorable (computer-assisted proof)
- Planarity testing: O(V) algorithm exists (Hopcroft-Tarjan, 1974)
Slide 12
Graph Coloring
- Assign colors to vertices such that no two adjacent vertices share a color. The minimum number of colors needed is the chromatic number chi(G).
- Bounds
- chi(G) >= clique number omega(G). chi(G)
- NP-Hard in General
- Determining chi(G) is NP-hard. Even deciding if chi(G)
- Applications
- Register allocation in compilers, scheduling problems, frequency assignment in wireless networks, map coloring, Sudoku.
Slide 13
Network Flow
- Model flow through a network from source s to sink t, respecting edge capacities. The max-flow min-cut theorem (Ford-Fulkerson, 1956) is a cornerstone.
- Max-Flow Min-Cut Theorem
- The maximum flow from s to t equals the minimum capacity of any s-t cut. A cut partitions vertices into S (containing s) and T (containing t).
- Algorithms
- Ford-Fulkerson: augmenting paths, O(E * max_flow)
- Edmonds-Karp: BFS augmentation, O(VE^2)
- Dinic's: blocking flows, O(V^2 * E)
- Push-relabel: O(V^2 * E) or O(V^3)
- Modern: nearly linear time for unit-capacity graphs
Slide 14
Matching Theory
- A matching is a set of edges with no shared vertices. Maximum matching finds the largest such set.
- Bipartite Matching
- Konig's theorem: in bipartite graphs, max matching = min vertex cover. Hungarian algorithm: O(V^3). Hopcroft-Karp: O(E * sqrt(V)).
- General Matching
- Edmonds' blossom algorithm (1965) solves maximum matching in general graphs in O(V^3). Uses "blossom" contraction for odd cycles.
- Hall's Marriage Theorem
- A bipartite graph has a perfect matching iff for every subset S of one side, |N(S)| >= |S|. The "marriage condition."
Slide 15
Random Graphs
- Erdos and Renyi (1959) initiated the study of random graphs G(n,p) where each edge exists independently with probability p.
- Phase transition at p = 1/n: below, all components are O(log n); above, a giant component of O(n) emerges
- Connectivity threshold: p = (ln n)/n -- below this, graph is almost surely disconnected
- Chromatic number: concentrates around n/(2 log_b n) where b = 1/(1-p)
- Erdos used probabilistic method: prove objects exist by showing random ones have desired properties with positive probability
- G(n,p) does NOT model real networks (no clustering, no power-law degrees)
Slide 16
Small-World and Scale-Free Networks
- Small-World (Watts-Strogatz, 1998)
- High clustering + short path lengths
- Start with ring lattice, rewire edges randomly
- "Six degrees of separation" phenomenon
- Models social networks, neural networks, power grids
- Scale-Free (Barabasi-Albert, 1999)
- Degree distribution follows power law: P(k) ~ k^(-gamma)
- Preferential attachment: "rich get richer"
- Hub-and-spoke structure
- Robust to random failures, vulnerable to targeted attacks
- Models: WWW, citation networks, protein interactions
Slide 17
Graph Algorithms in Practice
- PageRank (1998)
- Google's founding algorithm. Models the web as a directed graph. A page's rank equals the sum of ranks of pages linking to it, divided by their out-degrees. Computed via iterated matrix-vector multiplication.
- Community Detection
- Find densely connected clusters. Girvan-Newman (edge betweenness), Louvain (modularity optimization), spectral methods. Used in social network analysis.
- Influence Maximization
- Select k seed nodes to maximize spread in a network. NP-hard but greedy gives (1-1/e) approximation. Powers viral marketing strategies.
Slide 18
Ramsey Theory
- Ramsey theory asks: how large must a structure be to guarantee a particular ordered substructure? "Complete disorder is impossible."
- R(3,3) = 6: among any 6 people, there exist 3 mutual friends or 3 mutual strangers
- R(4,4) = 18: known. R(5,5): between 43 and 48 (open problem!)
- Erdos: "Imagine an alien force threatens to destroy Earth unless we determine R(5,5). We should marshal all computers and mathematicians. If they demand R(6,6), we should launch a preemptive strike."
- Upper bound (Erdos-Szekeres): R(r,s) Applications in information theory, geometry, and number theory
Slide 19
Spectral Graph Theory
- Study graphs through eigenvalues and eigenvectors of associated matrices (adjacency, Laplacian).
- Key Matrices
- Adjacency matrix A: A[i,j] = 1 if edge (i,j)
- Degree matrix D: diagonal, D[i,i] = deg(i)
- Laplacian L = D - A
- Normalized Laplacian: D^(-1/2) L D^(-1/2)
- Key Results
- Number of zero eigenvalues of L = number of components
- Second smallest eigenvalue (Fiedler value) measures connectivity
- Cheeger inequality relates spectral gap to expansion
- Spectral clustering: partition using Fiedler vector
- Largest eigenvalue of A bounded by max degree
Slide 20
Graph Minors and Robertson-Seymour
- A minor of G is obtained by deleting vertices/edges and contracting edges. The Robertson-Seymour theorem (proved 1983-2004, 20 papers, ~500 pages) states:
- Every minor-closed family of graphs can be characterized by a finite set of forbidden minors.
- Planar graphs: forbidden minors are K_5 and K_{3,3} (Wagner/Kuratowski)
- Graphs embeddable on torus: 17,523 forbidden minors (known)
- Linklessly embeddable graphs: Petersen family (7 forbidden minors)
- The theorem is non-constructive -- for most families, the forbidden minors are unknown
- Graph minor theory yields polynomial algorithms for many NP-hard problems on restricted graph classes
Slide 21
NP-Complete Graph Problems
- Many fundamental graph problems are NP-complete -- no known polynomial algorithm exists, and finding one would prove P = NP.
- ProblemDescriptionBest Known
- CliqueLargest complete subgraphO(1.1888^n)
- Independent SetLargest set of non-adjacent verticesO(1.1996^n)
- Vertex CoverSmallest set covering all edges2-approx poly; exact O(1.2^n)
- Graph ColoringMinimum colors for proper coloringO(2^n) exact
- Hamiltonian CycleCycle visiting all vertices onceO(2^n) dynamic programming
- Subgraph IsomorphismIs H a subgraph of G?O(n^|V(H)|) brute force
Slide 22
Approximation and Parameterized Algorithms
- Since exact solutions are intractable, we use approximation and parameterized complexity.
- Approximation
- Vertex Cover: 2-approximation (take both endpoints of a maximal matching). Max-Cut: 0.878-approx (Goemans-Williamson SDP). TSP (metric): 3/2-approx (Christofides).
- Fixed-Parameter Tractable (FPT)
- Vertex Cover of size k: O(2^k * n). Treewidth-based algorithms: many NP-hard problems solvable in O(f(tw) * n) via dynamic programming on tree decompositions.
- Practical Heuristics
- Simulated annealing, genetic algorithms, ant colony optimization. For TSP, LKH heuristic finds near-optimal solutions for millions of cities.
Slide 23
Graph Databases and Knowledge Graphs
- Graph theory powers modern data infrastructure for representing and querying interconnected data.
- Graph Databases
- Neo4j, Amazon Neptune, TigerGraph. Native graph storage with index-free adjacency. Query languages: Cypher, SPARQL, Gremlin. O(1) traversal per hop.
- Knowledge Graphs
- Google Knowledge Graph (500B+ facts), Wikidata, DBpedia. Entities as nodes, relationships as edges. Power search engines, recommendation systems, AI reasoning.
- Graph Neural Networks
- Message-passing neural networks on graph-structured data. GCN, GAT, GraphSAGE. Applications: drug discovery, material science, social recommendation, traffic prediction.
Slide 24
Social Network Analysis
- Graphs model social structures. Key metrics reveal patterns invisible to other methods.
- Centrality Measures
- Degree centrality: most connections
- Betweenness: lies on most shortest paths (brokers)
- Closeness: smallest average distance to all others
- Eigenvector: connected to other important nodes
- PageRank: random-walk based importance
- Network Properties
- Clustering coefficient: how cliquish are neighborhoods
- Diameter: longest shortest path
- Average path length: typically O(log n) in social nets
- Degree distribution: power-law in most real networks
- Homophily: tendency to connect with similar others
Slide 25
Extremal Graph Theory
- What is the maximum number of edges a graph can have while avoiding a specific subgraph?
- Turan's theorem (1941): maximum edges in K_{r+1}-free graph on n vertices is (1 - 1/r) * n^2 / 2. Achieved by complete r-partite graph.
- Zarankiewicz problem: maximum edges in K_{s,t}-free bipartite graph. Upper bound: O(n^{2-1/s}) for s Erdos-Stone theorem: generalizes Turan -- density threshold for containing H as subgraph is 1 - 1/(chi(H)-1).
- Szemeredi regularity lemma: any dense graph can be approximated by a bounded-complexity structure.
- These results connect combinatorics to analysis, topology, and additive number theory.
Slide 26
Graph Isomorphism
- Are two graphs structurally identical (same up to relabeling)? One of the few natural problems believed to be neither in P nor NP-complete.
- Status
- Babai (2015): quasipolynomial time O(exp(log^c n)). Not yet known to be in P. Known to be in co-AM (probably not NP-complete).
- Practical Algorithms
- McKay's nauty/Traces: extremely fast in practice using canonical labeling and automorphism group computation. Handles graphs with millions of vertices.
- Polynomial Cases
- Planar graphs, bounded-degree graphs, bounded treewidth, interval graphs. Many structured graph classes admit efficient isomorphism testing.
Slide 27
Topological Graph Theory
- Which surfaces can a graph be embedded on without crossings?
- Genus g(G): minimum number of handles needed. Planar = genus 0. K_5 has genus 1 (embeds on torus).
- Euler's formula generalized: V - E + F = 2 - 2g for orientable surfaces of genus g
- Heawood conjecture (1890, proved 1968): every graph on surface of genus g >= 1 is chi-colorable where chi = floor((7 + sqrt(1 + 48g))/2)
- Crossing number cr(G): minimum edge crossings in any plane drawing. cr(K_n) is still unknown for general n!
- Graph drawing: algorithms for aesthetically pleasing, low-crossing layouts (force-directed, layered, orthogonal)
Slide 28
Historical Milestones
- 1736
- Euler solves Konigsberg bridges problem -- birth of graph theory
- 1852
- Four-color conjecture posed by Francis Guthrie
- 1936
- Konig publishes first textbook on graph theory
- 1959
- Erdos-Renyi random graphs; Dijkstra's shortest-path algorithm
- 1965
- Edmonds' blossom algorithm for general matching
- 1976
- Four Color Theorem proved (Appel and Haken, first major computer-assisted proof)
- 2004
- Robertson-Seymour theorem completed (graph minor structure theorem)
- 2015
- Babai's quasipolynomial graph isomorphism algorithm
Slide 29
Open Problems
- P vs NP
- Can every graph problem whose solution is quickly verifiable also be quickly solved? Most important open problem in theoretical CS. $1M Millennium Prize.
- Hadwiger's Conjecture
- Every graph with chi(G) >= k contains K_k as a minor. Proved for k = 7. Strengthens the Four Color Theorem.
- Reconstruction Conjecture
- Is every graph with 3+ vertices determined (up to isomorphism) by its collection of vertex-deleted subgraphs? Open since 1942 (Kelly-Ulam).
- Graceful Labeling
- Can every tree be gracefully labeled? (Ringel-Kotzig conjecture, 1967). Proved for trees up to 35 vertices. General case remains open.
Slide 30
Computational Complexity Classes
- Graph problems span the complexity landscape:
- ClassExample Graph Problems
- L (log-space)Undirected connectivity (Reingold, 2004)
- PShortest path, matching, MST, 2-coloring, planarity
- NP-completeClique, Hamiltonian cycle, 3-coloring, TSP
- co-NPGraph non-isomorphism (also in AM)
- GI-completeGraph isomorphism (quasipoly, status unclear)
- #P-completeCounting perfect matchings, counting colorings
- PSPACEGeneralized geography games on graphs
Slide 31
Modern Applications
- Internet Routing
- BGP, OSPF use shortest-path algorithms on the AS-level graph of ~75,000 nodes.
- Bioinformatics
- Genome assembly via Eulerian paths on de Bruijn graphs. Protein interaction networks.
- Chip Design
- VLSI placement and routing as graph partitioning and Steiner tree problems.
- Epidemiology
- Contact tracing graphs. SIR models on networks. Vaccination strategies via centrality.
- Logistics
- Vehicle routing (TSP variants), supply chain optimization, airline scheduling.
- Recommendation
- Collaborative filtering as bipartite graph link prediction. GNNs for item graphs.
Slide 32
Key Takeaways
- Universal Abstraction
- Any system of pairwise relationships can be modeled as a graph. This makes graph theory the lingua franca of discrete mathematics and computer science.
- Algorithms Power the World
- From GPS navigation (Dijkstra) to web search (PageRank) to social feeds (community detection), graph algorithms process billions of queries daily.
- Deep Unsolved Questions
- P vs NP, Hadwiger's conjecture, reconstruction -- graph theory contains some of the deepest open problems in all of mathematics.
- Growing Relevance
- GNNs, knowledge graphs, and network science ensure graph theory's importance only increases as the world becomes more connected.
- -- End --
