# Graph Theory

Canonical URL: https://shipslides.com/d/mathematics-graph-theory
Raw viewer URL: https://content.shipslides.com/d/mathematics-graph-theory/raw
Category: Mathematics
Slides: 32
Updated: 2026-05-17T20:51:31.677Z
Tags: mathematics, graph, theory

## Summary

The Mathematics of Connection Key sections include: Graph Theory; Origins: The Bridges of Konigsberg; Fundamental Definitions; The Handshaking Lemma; Special Graph Families; Paths, Cycles, and Connectivity; Trees and Spanning Trees; Graph Traversal Algorithms; Shortest Path Algorithms; Euler and Hamilton Paths.

## Slide Outline

1. Graph Theory
2. Origins: The Bridges of Konigsberg
3. Fundamental Definitions
4. The Handshaking Lemma
5. Special Graph Families
6. Paths, Cycles, and Connectivity
7. Trees and Spanning Trees
8. Graph Traversal Algorithms
9. Shortest Path Algorithms
10. Euler and Hamilton Paths
11. Planar Graphs
12. Graph Coloring
13. Network Flow
14. Matching Theory
15. Random Graphs
16. Small-World and Scale-Free Networks
17. Graph Algorithms in Practice
18. Ramsey Theory
19. Spectral Graph Theory
20. Graph Minors and Robertson-Seymour
21. NP-Complete Graph Problems
22. Approximation and Parameterized Algorithms
23. Graph Databases and Knowledge Graphs
24. Social Network Analysis
25. Extremal Graph Theory
26. Graph Isomorphism
27. Topological Graph Theory
28. Historical Milestones
29. Open Problems
30. Computational Complexity Classes
31. Modern Applications
32. Key Takeaways

## Slide Transcript

### Slide 1: 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 2: 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 3: 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 4: 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 5: 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 6: 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 7: 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 8: 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 9: 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 --


## Related Decks

- [Game Theory · Deep](https://shipslides.com/d/mathematics-game-theory-deep)
- [Number Theory](https://shipslides.com/d/mathematics-number-theory)
- [Topology](https://shipslides.com/d/mathematics-topology)
- [Algebra](https://shipslides.com/d/mathematics-algebra)